Merge pull request #134 from junegunn/devel

0.9.4

20 files changed, 494 insertions, 142 deletions

diff --git a/.travis.yml b/.travis.yml
index 692ade7a..69086778 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,11 +1,15 @@
 language: ruby
+rvm:
+- 2.2.0
 
 install:
 - sudo apt-get update
 - sudo apt-get install -y libncurses-dev lib32ncurses5-dev
 - sudo add-apt-repository -y ppa:pi-rho/dev
+- sudo apt-add-repository -y ppa:fish-shell/release-2
 - sudo apt-get update
 - sudo apt-get install -y tmux=1.9a-1~ppa1~p
+- sudo apt-get install -y zsh fish
 
 script: |
   export GOROOT=~/go1.4
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 00000000..b9e8e773
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,60 @@
+CHANGELOG
+=========
+
+0.9.4
+-----
+
+### New features
+
+#### Added `--tac` option to reverse the order of the input.
+
+One might argue that this option is unnecessary since we can already put `tac`
+or `tail -r` in the command pipeline to achieve the same result. However, the
+advantage of `--tac` is that it does not block until the input is complete.
+
+### *Backward incompatible changes*
+
+#### Changed behavior on `--no-sort`
+
+`--no-sort` option will no longer reverse the display order within finder. You
+may want to use the new `--tac` option with `--no-sort`.
+
+```
+history | fzf +s --tac
+```
+
+### Improvements
+
+#### `--filter` will not block when sort is disabled
+
+When fzf works in filtering mode (`--filter`) and sort is disabled
+(`--no-sort`), there's no need to block until input is complete. The new
+version of fzf will print the matches on-the-fly when the following condition
+is met:
+
+    --filter TERM --no-sort [--no-tac --no-sync]
+
+or simply:
+
+    -f TERM +s
+
+This change removes unnecessary delay in the use cases like the following:
+
+    fzf -f xxx +s | head -5
+
+However, in this case, fzf processes the lines sequentially, so it cannot
+utilize multiple cores, and fzf will run slightly slower than the previous
+mode of execution where filtering is done in parallel after the entire input
+is loaded. If the user is concerned about this performance problem, one can
+add `--sync` option to re-enable buffering.
+
+0.9.3
+-----
+
+### New features
+- Added `--sync` option for multi-staged filtering
+
+### Improvements
+- `--select-1` and `--exit-0` will start finder immediately when the condition
+  cannot be met
+
diff --git a/README.md b/README.md
index 16cedbfa..e5ada36b 100644
--- a/README.md
+++ b/README.md
@@ -75,7 +75,7 @@ Usage
 ```
 usage: fzf [options]
 
-  Search
+  Search mode
     -x, --extended        Extended-search mode
     -e, --extended-exact  Extended-search mode (exact match)
     -i                    Case-insensitive match (default: smart-case match)
@@ -87,8 +87,9 @@ usage: fzf [options]
     -d, --delimiter=STR   Field delimiter regex for --nth (default: AWK-style)
 
   Search result
-    -s, --sort            Sort the result
-    +s, --no-sort         Do not sort the result. Keep the sequence unchanged.
+    +s, --no-sort         Do not sort the result
+        --tac             Reverse the order of the input
+                          (e.g. 'history | fzf --tac --no-sort')
 
   Interface
     -m, --multi           Enable multi-select with tab/shift-tab
@@ -128,13 +129,6 @@ files excluding hidden ones. (You can override the default command with
 vim $(fzf)
 ```
 
-If you want to preserve the exact sequence of the input, provide `--no-sort` (or
-`+s`) option.
-
-```sh
-history | fzf +s
-```
-
 ### Keys
 
 Use CTRL-J and CTRL-K (or CTRL-N and CTRL-P) to change the selection, press
@@ -197,7 +191,7 @@ fd() {
 
 # fh - repeat history
 fh() {
-  eval $(([ -n "$ZSH_NAME" ] && fc -l 1 || history) | fzf +s | sed 's/ *[0-9]* *//')
+  eval $(([ -n "$ZSH_NAME" ] && fc -l 1 || history) | fzf +s --tac | sed 's/ *[0-9]* *//')
 }
 
 # fkill - kill process
diff --git a/install b/install
index 5cd06728..8b53f721 100755
--- a/install
+++ b/install
@@ -1,6 +1,6 @@
 #!/usr/bin/env bash
 
-version=0.9.3
+version=0.9.4
 
 cd $(dirname $BASH_SOURCE)
 fzf_base=$(pwd)
@@ -245,7 +245,7 @@ if [ -z "$(set -o | \grep '^vi.*on')" ]; then
   fi
 
   # CTRL-R - Paste the selected command from history into the command line
-  bind '"\C-r": " \C-e\C-u$(HISTTIMEFORMAT= history | fzf +s +m -n2..,.. | sed \"s/ *[0-9]* *//\")\e\C-e\er"'
+  bind '"\C-r": " \C-e\C-u$(HISTTIMEFORMAT= history | fzf +s --tac +m -n2..,.. | sed \"s/ *[0-9]* *//\")\e\C-e\er"'
 
   # ALT-C - cd into the selected directory
   bind '"\ec": " \C-e\C-u$(__fcd)\e\C-e\er\C-m"'
@@ -263,7 +263,7 @@ else
   bind -m vi-command '"\C-t": "i\C-t"'
 
   # CTRL-R - Paste the selected command from history into the command line
-  bind '"\C-r": "\eddi$(HISTTIMEFORMAT= history | fzf +s +m -n2..,.. | sed \"s/ *[0-9]* *//\")\C-x\C-e\e$a\C-x\C-r"'
+  bind '"\C-r": "\eddi$(HISTTIMEFORMAT= history | fzf +s --tac +m -n2..,.. | sed \"s/ *[0-9]* *//\")\C-x\C-e\e$a\C-x\C-r"'
   bind -m vi-command '"\C-r": "i\C-r"'
 
   # ALT-C - cd into the selected directory
@@ -323,7 +323,7 @@ bindkey '\ec' fzf-cd-widget
 
 # CTRL-R - Paste the selected command from history into the command line
 fzf-history-widget() {
-  LBUFFER=$(fc -l 1 | fzf +s +m -n2..,.. | sed "s/ *[0-9*]* *//")
+  LBUFFER=$(fc -l 1 | fzf +s --tac +m -n2..,.. | sed "s/ *[0-9*]* *//")
   zle redisplay
 }
 zle     -N   fzf-history-widget
@@ -412,7 +412,7 @@ function fzf_key_bindings
   end
 
   function __fzf_ctrl_r
-    history | __fzf_reverse | fzf +s +m > $TMPDIR/fzf.result
+    history | __fzf_reverse | fzf +s --tac +m > $TMPDIR/fzf.result
     and commandline (cat $TMPDIR/fzf.result)
     commandline -f repaint
     rm -f $TMPDIR/fzf.result
diff --git a/src/Dockerfile.arch b/src/Dockerfile.arch
index e37a8b22..b5fd7c08 100644
--- a/src/Dockerfile.arch
+++ b/src/Dockerfile.arch
@@ -6,7 +6,7 @@ RUN pacman-db-upgrade && pacman -Syu --noconfirm base-devel git
 
 # Install Go 1.4
 RUN cd / && curl \
-    https://storage.googleapis.com/golang/go1.4.1.linux-amd64.tar.gz | \
+    https://storage.googleapis.com/golang/go1.4.2.linux-amd64.tar.gz | \
     tar -xz && mv go go1.4
 
 ENV GOPATH /go
diff --git a/src/Dockerfile.centos b/src/Dockerfile.centos
index bbe065e6..c03f43a2 100644
--- a/src/Dockerfile.centos
+++ b/src/Dockerfile.centos
@@ -6,7 +6,7 @@ RUN yum install -y git gcc make tar ncurses-devel
 
 # Install Go 1.4
 RUN cd / && curl \
-    https://storage.googleapis.com/golang/go1.4.1.linux-amd64.tar.gz | \
+    https://storage.googleapis.com/golang/go1.4.2.linux-amd64.tar.gz | \
     tar -xz && mv go go1.4
 
 ENV GOPATH /go
diff --git a/src/Dockerfile.ubuntu b/src/Dockerfile.ubuntu
index 9d28b322..4778a6d1 100644
--- a/src/Dockerfile.ubuntu
+++ b/src/Dockerfile.ubuntu
@@ -7,7 +7,7 @@ RUN apt-get update && apt-get -y upgrade && \
 
 # Install Go 1.4
 RUN cd / && curl \
-    https://storage.googleapis.com/golang/go1.4.1.linux-amd64.tar.gz | \
+    https://storage.googleapis.com/golang/go1.4.2.linux-amd64.tar.gz | \
     tar -xz && mv go go1.4
 
 ENV GOPATH /go
diff --git a/src/constants.go b/src/constants.go
index 7d542234..f5138534 100644
--- a/src/constants.go
+++ b/src/constants.go
@@ -5,7 +5,7 @@ import (
 )
 
 // Current version
-const Version = "0.9.3"
+const Version = "0.9.4"
 
 // fzf events
 const (
diff --git a/src/core.go b/src/core.go
index ea97b4e6..62190d08 100644
--- a/src/core.go
+++ b/src/core.go
@@ -85,33 +85,47 @@ func Run(options *Options) {
 	}
 
 	// Reader
-	reader := Reader{func(str string) { chunkList.Push(str) }, eventBox}
-	go reader.ReadSource()
+	streamingFilter := opts.Filter != nil && opts.Sort == 0 && !opts.Tac && !opts.Sync
+	if !streamingFilter {
+		reader := Reader{func(str string) { chunkList.Push(str) }, eventBox}
+		go reader.ReadSource()
+	}
 
 	// Matcher
 	patternBuilder := func(runes []rune) *Pattern {
 		return BuildPattern(
 			opts.Mode, opts.Case, opts.Nth, opts.Delimiter, runes)
 	}
-	matcher := NewMatcher(patternBuilder, opts.Sort > 0, eventBox)
+	matcher := NewMatcher(patternBuilder, opts.Sort > 0, opts.Tac, eventBox)
 
 	// Filtering mode
 	if opts.Filter != nil {
-		pattern := patternBuilder([]rune(*opts.Filter))
-
-		eventBox.Unwatch(EvtReadNew)
-		eventBox.WaitFor(EvtReadFin)
-
-		snapshot, _ := chunkList.Snapshot()
-		merger, _ := matcher.scan(MatchRequest{
-			chunks:  snapshot,
-			pattern: pattern})
-
 		if opts.PrintQuery {
 			fmt.Println(*opts.Filter)
 		}
-		for i := 0; i < merger.Length(); i++ {
-			fmt.Println(merger.Get(i).AsString())
+
+		pattern := patternBuilder([]rune(*opts.Filter))
+
+		if streamingFilter {
+			reader := Reader{
+				func(str string) {
+					item := chunkList.trans(&str, 0)
+					if pattern.MatchItem(item) {
+						fmt.Println(*item.text)
+					}
+				}, eventBox}
+			reader.ReadSource()
+		} else {
+			eventBox.Unwatch(EvtReadNew)
+			eventBox.WaitFor(EvtReadFin)
+
+			snapshot, _ := chunkList.Snapshot()
+			merger, _ := matcher.scan(MatchRequest{
+				chunks:  snapshot,
+				pattern: pattern})
+			for i := 0; i < merger.Length(); i++ {
+				fmt.Println(merger.Get(i).AsString())
+			}
 		}
 		os.Exit(0)
 	}
diff --git a/src/item.go b/src/item.go
index 4cbd3f98..2b8a9d13 100644
--- a/src/item.go
+++ b/src/item.go
@@ -87,10 +87,28 @@ func (a ByRelevance) Less(i, j int) bool {
 	irank := a[i].Rank(true)
 	jrank := a[j].Rank(true)
 
-	return compareRanks(irank, jrank)
+	return compareRanks(irank, jrank, false)
 }
 
-func compareRanks(irank Rank, jrank Rank) bool {
+// ByRelevanceTac is for sorting Items
+type ByRelevanceTac []*Item
+
+func (a ByRelevanceTac) Len() int {
+	return len(a)
+}
+
+func (a ByRelevanceTac) Swap(i, j int) {
+	a[i], a[j] = a[j], a[i]
+}
+
+func (a ByRelevanceTac) Less(i, j int) bool {
+	irank := a[i].Rank(true)
+	jrank := a[j].Rank(true)
+
+	return compareRanks(irank, jrank, true)
+}
+
+func compareRanks(irank Rank, jrank Rank, tac bool) bool {
 	if irank.matchlen < jrank.matchlen {
 		return true
 	} else if irank.matchlen > jrank.matchlen {
@@ -103,8 +121,5 @@ func compareRanks(irank Rank, jrank Rank) bool {
 		return false
 	}
 
-	if irank.index <= jrank.index {
-		return true
-	}
-	return false
+	return (irank.index <= jrank.index) != tac
 }
diff --git a/src/item_test.go b/src/item_test.go
index 0e83631a..372ab4ae 100644
--- a/src/item_test.go
+++ b/src/item_test.go
@@ -20,12 +20,19 @@ func TestOffsetSort(t *testing.T) {
 }
 
 func TestRankComparison(t *testing.T) {
-	if compareRanks(Rank{3, 0, 5}, Rank{2, 0, 7}) ||
-		!compareRanks(Rank{3, 0, 5}, Rank{3, 0, 6}) ||
-		!compareRanks(Rank{1, 2, 3}, Rank{1, 3, 2}) ||
-		!compareRanks(Rank{0, 0, 0}, Rank{0, 0, 0}) {
+	if compareRanks(Rank{3, 0, 5}, Rank{2, 0, 7}, false) ||
+		!compareRanks(Rank{3, 0, 5}, Rank{3, 0, 6}, false) ||
+		!compareRanks(Rank{1, 2, 3}, Rank{1, 3, 2}, false) ||
+		!compareRanks(Rank{0, 0, 0}, Rank{0, 0, 0}, false) {
 		t.Error("Invalid order")
 	}
+
+	if compareRanks(Rank{3, 0, 5}, Rank{2, 0, 7}, true) ||
+		!compareRanks(Rank{3, 0, 5}, Rank{3, 0, 6}, false) ||
+		!compareRanks(Rank{1, 2, 3}, Rank{1, 3, 2}, true) ||
+		!compareRanks(Rank{0, 0, 0}, Rank{0, 0, 0}, false) {
+		t.Error("Invalid order (tac)")
+	}
 }
 
 // Match length, string length, index
diff --git a/src/matcher.go b/src/matcher.go
index bfe9d287..0879a088 100644
--- a/src/matcher.go
+++ b/src/matcher.go
@@ -21,6 +21,7 @@ type MatchRequest struct {
 type Matcher struct {
 	patternBuilder func([]rune) *Pattern
 	sort           bool
+	tac            bool
 	eventBox       *util.EventBox
 	reqBox         *util.EventBox
 	partitions     int
@@ -38,10 +39,11 @@ const (
 
 // NewMatcher returns a new Matcher
 func NewMatcher(patternBuilder func([]rune) *Pattern,
-	sort bool, eventBox *util.EventBox) *Matcher {
+	sort bool, tac bool, eventBox *util.EventBox) *Matcher {
 	return &Matcher{
 		patternBuilder: patternBuilder,
 		sort:           sort,
+		tac:            tac,
 		eventBox:       eventBox,
 		reqBox:         util.NewEventBox(),
 		partitions:     runtime.NumCPU(),
@@ -159,7 +161,11 @@ func (m *Matcher) scan(request MatchRequest) (*Merger, bool) {
 				countChan <- len(matches)
 			}
 			if !empty && m.sort {
-				sort.Sort(ByRelevance(sliceMatches))
+				if m.tac {
+					sort.Sort(ByRelevanceTac(sliceMatches))
+				} else {
+					sort.Sort(ByRelevance(sliceMatches))
+				}
 			}
 			resultChan <- partialResult{idx, sliceMatches}
 		}(idx, chunks)
@@ -195,7 +201,7 @@ func (m *Matcher) scan(request MatchRequest) (*Merger, bool) {
 		partialResult := <-resultChan
 		partialResults[partialResult.index] = partialResult.matches
 	}
-	return NewMerger(partialResults, !empty && m.sort), false
+	return NewMerger(partialResults, !empty && m.sort, m.tac), false
 }
 
 // Reset is called to interrupt/signal the ongoing search
diff --git a/src/merger.go b/src/merger.go
index 5bfc81d5..41323c18 100644
--- a/src/merger.go
+++ b/src/merger.go
@@ -3,7 +3,7 @@ package fzf
 import "fmt"
 
 // Merger with no data
-var EmptyMerger = NewMerger([][]*Item{}, false)
+var EmptyMerger = NewMerger([][]*Item{}, false, false)
 
 // Merger holds a set of locally sorted lists of items and provides the view of
 // a single, globally-sorted list
@@ -12,17 +12,19 @@ type Merger struct {
 	merged  []*Item
 	cursors []int
 	sorted  bool
+	tac     bool
 	final   bool
 	count   int
 }
 
 // NewMerger returns a new Merger
-func NewMerger(lists [][]*Item, sorted bool) *Merger {
+func NewMerger(lists [][]*Item, sorted bool, tac bool) *Merger {
 	mg := Merger{
 		lists:   lists,
 		merged:  []*Item{},
 		cursors: make([]int, len(lists)),
 		sorted:  sorted,
+		tac:     tac,
 		final:   false,
 		count:   0}
 
@@ -39,19 +41,21 @@ func (mg *Merger) Length() int {
 
 // Get returns the pointer to the Item object indexed by the given integer
 func (mg *Merger) Get(idx int) *Item {
-	if len(mg.lists) == 1 {
-		return mg.lists[0][idx]
-	} else if !mg.sorted {
-		for _, list := range mg.lists {
-			numItems := len(list)
-			if idx < numItems {
-				return list[idx]
-			}
-			idx -= numItems
+	if mg.sorted {
+		return mg.mergedGet(idx)
+	}
+
+	if mg.tac {
+		idx = mg.Length() - idx - 1
+	}
+	for _, list := range mg.lists {
+		numItems := len(list)
+		if idx < numItems {
+			return list[idx]
 		}
-		panic(fmt.Sprintf("Index out of bounds (unsorted, %d/%d)", idx, mg.count))
+		idx -= numItems
 	}
-	return mg.mergedGet(idx)
+	panic(fmt.Sprintf("Index out of bounds (unsorted, %d/%d)", idx, mg.count))
 }
 
 func (mg *Merger) mergedGet(idx int) *Item {
@@ -66,7 +70,7 @@ func (mg *Merger) mergedGet(idx int) *Item {
 			}
 			if cursor >= 0 {
 				rank := list[cursor].Rank(false)
-				if minIdx < 0 || compareRanks(rank, minRank) {
+				if minIdx < 0 || compareRanks(rank, minRank, mg.tac) {
 					minRank = rank
 					minIdx = listIdx
 				}
diff --git a/src/merger_test.go b/src/merger_test.go
index f79da09a..b69d6338 100644
--- a/src/merger_test.go
+++ b/src/merger_test.go
@@ -62,7 +62,7 @@ func TestMergerUnsorted(t *testing.T) {
 	cnt := len(items)
 
 	// Not sorted: same order
-	mg := NewMerger(lists, false)
+	mg := NewMerger(lists, false, false)
 	assert(t, cnt == mg.Length(), "Invalid Length")
 	for i := 0; i < cnt; i++ {
 		assert(t, items[i] == mg.Get(i), "Invalid Get")
@@ -74,7 +74,7 @@ func TestMergerSorted(t *testing.T) {
 	cnt := len(items)
 
 	// Sorted sorted order
-	mg := NewMerger(lists, true)
+	mg := NewMerger(lists, true, false)
 	assert(t, cnt == mg.Length(), "Invalid Length")
 	sort.Sort(ByRelevance(items))
 	for i := 0; i < cnt; i++ {
@@ -84,7 +84,7 @@ func TestMergerSorted(t *testing.T) {
 	}
 
 	// Inverse order
-	mg2 := NewMerger(lists, true)
+	mg2 := NewMerger(lists, true, false)
 	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 c426e777..dc8f0b84 100644
--- a/src/options.go
+++ b/src/options.go
@@ -11,7 +11,7 @@ import (
 
 const usage = `usage: fzf [options]
 
-  Search
+  Search mode
     -x, --extended        Extended-search mode
     -e, --extended-exact  Extended-search mode (exact match)
     -i                    Case-insensitive match (default: smart-case match)
@@ -23,8 +23,9 @@ const usage = `usage: fzf [options]
     -d, --delimiter=STR   Field delimiter regex for --nth (default: AWK-style)
 
   Search result
-    -s, --sort            Sort the result
-    +s, --no-sort         Do not sort the result. Keep the sequence unchanged.
+    +s, --no-sort         Do not sort the result
+        --tac             Reverse the order of the input
+                          (e.g. 'history | fzf --tac --no-sort')
 
   Interface
     -m, --multi           Enable multi-select with tab/shift-tab
@@ -78,6 +79,7 @@ type Options struct {
 	WithNth    []Range
 	Delimiter  *regexp.Regexp
 	Sort       int
+	Tac        bool
 	Multi      bool
 	Mouse      bool
 	Color      bool
@@ -102,6 +104,7 @@ func defaultOptions() *Options {
 		WithNth:    make([]Range, 0),
 		Delimiter:  nil,
 		Sort:       1000,
+		Tac:        false,
 		Multi:      false,
 		Mouse:      true,
 		Color:      true,
@@ -212,6 +215,10 @@ func parseOptions(opts *Options, allArgs []string) {
 			opts.Sort = optionalNumeric(allArgs, &i)
 		case "+s", "--no-sort":
 			opts.Sort = 0
+		case "--tac":
+			opts.Tac = true
+		case "--no-tac":
+			opts.Tac = false
 		case "-i":
 			opts.Case = CaseIgnore
 		case "+i":
diff --git a/src/pattern.go b/src/pattern.go
index 17e3b6b8..725ce2db 100644
--- a/src/pattern.go
+++ b/src/pattern.go
@@ -219,12 +219,7 @@ Loop:
 		}
 	}
 
-	var matches []*Item
-	if p.mode == ModeFuzzy {
-		matches = p.fuzzyMatch(space)
-	} else {
-		matches = p.extendedMatch(space)
-	}
+	matches := p.matchChunk(space)
 
 	if !p.hasInvTerm {
 		_cache.Add(chunk, cacheKey, matches)
@@ -232,6 +227,35 @@ Loop:
 	return matches
 }
 
+func (p *Pattern) matchChunk(chunk *Chunk) []*Item {
+	matches := []*Item{}
+	if p.mode == ModeFuzzy {
+		for _, item := range *chunk {
+			if sidx, eidx := p.fuzzyMatch(item); sidx >= 0 {
+				matches = append(matches,
+					dupItem(item, []Offset{Offset{int32(sidx), int32(eidx)}}))
+			}
+		}
+	} else {
+		for _, item := range *chunk {
+			if offsets := p.extendedMatch(item); len(offsets) == len(p.terms) {
+				matches = append(matches, dupItem(item, offsets))
+			}
+		}
+	}
+	return matches
+}
+
+// MatchItem returns true if the Item is a match
+func (p *Pattern) MatchItem(item *Item) bool {
+	if p.mode == ModeFuzzy {
+		sidx, _ := p.fuzzyMatch(item)
+		return sidx >= 0
+	}
+	offsets := p.extendedMatch(item)
+	return len(offsets) == len(p.terms)
+}
+
 func dupItem(item *Item, offsets []Offset) *Item {
 	sort.Sort(ByOrder(offsets))
 	return &Item{
@@ -243,39 +267,26 @@ func dupItem(item *Item, offsets []Offset) *Item {
 		rank:        Rank{0, 0, item.index}}
 }
 
-func (p *Pattern) fuzzyMatch(chunk *Chunk) []*Item {
-	matches := []*Item{}
-	for _, item := range *chunk {
-		input := p.prepareInput(item)
-		if sidx, eidx := p.iter(algo.FuzzyMatch, input, p.text); sidx >= 0 {
-			matches = append(matches,
-				dupItem(item, []Offset{Offset{int32(sidx), int32(eidx)}}))
-		}
-	}
-	return matches
+func (p *Pattern) fuzzyMatch(item *Item) (int, int) {
+	input := p.prepareInput(item)
+	return p.iter(algo.FuzzyMatch, input, p.text)
 }
 
-func (p *Pattern) extendedMatch(chunk *Chunk) []*Item {
-	matches := []*Item{}
-	for _, item := range *chunk {
-		input := p.prepareInput(item)
-		offsets := []Offset{}
-		for _, term := range p.terms {
-			pfun := p.procFun[term.typ]
-			if sidx, eidx := p.iter(pfun, input, term.text); sidx >= 0 {
-				if term.inv {
-					break
-				}
-				offsets = append(offsets, Offset{int32(sidx), int32(eidx)})
-			} else if term.inv {
-				offsets = append(offsets, Offset{0, 0})
+func (p *Pattern) extendedMatch(item *Item) []Offset {
+	input := p.prepareInput(item)
+	offsets := []Offset{}
+	for _, term := range p.terms {
+		pfun := p.procFun[term.typ]
+		if sidx, eidx := p.iter(pfun, input, term.text); sidx >= 0 {
+			if term.inv {
+				break
 			}
-		}
-		if len(offsets) == len(p.terms) {
-			matches = append(matches, dupItem(item, offsets))
+			offsets = append(offsets, Offset{int32(sidx), int32(eidx)})
+		} else if term.inv {
+			offsets = append(offsets, Offset{0, 0})
 		}
 	}
-	return matches
+	return offsets
 }
 
 func (p *Pattern) prepareInput(item *Item) *Transformed {
diff --git a/src/pattern_test.go b/src/pattern_test.go
index 4d36eda5..67542f21 100644
--- a/src/pattern_test.go
+++ b/src/pattern_test.go
@@ -98,14 +98,15 @@ func TestOrigTextAndTransformed(t *testing.T) {
 	tokens := Tokenize(strptr("junegunn"), nil)
 	trans := Transform(tokens, []Range{Range{1, 1}})
 
-	for _, fun := range []func(*Chunk) []*Item{pattern.fuzzyMatch, pattern.extendedMatch} {
+	for _, mode := range []Mode{ModeFuzzy, ModeExtended} {
 		chunk := Chunk{
 			&Item{
 				text:        strptr("junegunn"),
 				origText:    strptr("junegunn.choi"),
 				transformed: trans},
 		}
-		matches := fun(&chunk)
+		pattern.mode = mode
+		matches := pattern.matchChunk(&chunk)
 		if *matches[0].text != "junegunn" || *matches[0].origText != "junegunn.choi" ||
 			matches[0].offsets[0][0] != 0 || matches[0].offsets[0][1] != 5 ||
 			matches[0].transformed != trans {
diff --git a/src/terminal.go b/src/terminal.go
index 3d914ac5..bd426d1a 100644
--- a/src/terminal.go
+++ b/src/terminal.go
@@ -22,7 +22,6 @@ import (
 type Terminal struct {
 	prompt     string
 	reverse    bool
-	tac        bool
 	cx         int
 	cy         int
 	offset     int
@@ -85,7 +84,6 @@ func NewTerminal(opts *Options, eventBox *util.EventBox) *Terminal {
 	input := []rune(opts.Query)
 	return &Terminal{
 		prompt:     opts.Prompt,
-		tac:        opts.Sort == 0,
 		reverse:    opts.Reverse,
 		cx:         len(input),
 		cy:         0,
@@ -148,13 +146,6 @@ func (t *Terminal) UpdateList(merger *Merger) {
 	t.reqBox.Set(reqList, nil)
 }
 
-func (t *Terminal) listIndex(y int) int {
-	if t.tac {
-		return t.merger.Length() - y - 1
-	}
-	return y
-}
-
 func (t *Terminal) output() {
 	if t.printQuery {
 		fmt.Println(string(t.input))
@@ -162,7 +153,7 @@ func (t *Terminal) output() {
 	if len(t.selected) == 0 {
 		cnt := t.merger.Length()
 		if cnt > 0 && cnt > t.cy {
-			fmt.Println(t.merger.Get(t.listIndex(t.cy)).AsString())
+			fmt.Println(t.merger.Get(t.cy).AsString())
 		}
 	} else {
 		sels := make([]selectedItem, 0, len(t.selected))
@@ -246,7 +237,7 @@ func (t *Terminal) printList() {
 	for i := 0; i < maxy; i++ {
 		t.move(i+2, 0, true)
 		if i < count {
-			t.printItem(t.merger.Get(t.listIndex(i+t.offset)), i == t.cy-t.offset)
+			t.printItem(t.merger.Get(i+t.offset), i == t.cy-t.offset)
 		}
 	}
 }
@@ -525,9 +516,8 @@ func (t *Terminal) Loop() {
 			}
 		}
 		toggle := func() {
-			idx := t.listIndex(t.cy)
-			if idx < t.merger.Length() {
-				item := t.merger.Get(idx)
+			if t.cy < t.merger.Length() {
+				item := t.merger.Get(t.cy)
 				if _, found := t.selected[item.text]; !found {
 					var strptr *string
 					if item.origText != nil {
@@ -650,7 +640,7 @@ func (t *Terminal) Loop() {
 			} else if me.Double {
 				// Double-click
 				if my >= 2 {
-					if t.vset(my-2) && t.listIndex(t.cy) < t.merger.Length() {
+					if t.vset(my-2) && t.cy < t.merger.Length() {
 						req(reqClose)
 					}
 				}
diff --git a/test/test_go.rb b/test/test_go.rb
index fe32a4ea..6aa438b0 100644
--- a/test/test_go.rb
+++ b/test/test_go.rb
@@ -2,11 +2,20 @@
 # encoding: utf-8
 
 require 'minitest/autorun'
+require 'fileutils'
 
 class NilClass
   def include? str
     false
   end
+
+  def start_with? str
+    false
+  end
+
+  def end_with? str
+    false
+  end
 end
 
 module Temp
@@ -15,7 +24,7 @@ module Temp
     waited = 0
     while waited < 5
       begin
-        data = File.read(name)
+        data = `cat #{name}`
         return data unless data.empty?
       rescue
         sleep 0.1
@@ -30,6 +39,20 @@ module Temp
   end
 end
 
+class Shell
+  class << self
+    def bash
+      'PS1= PROMPT_COMMAND= bash --rcfile ~/.fzf.bash'
+    end
+
+    def zsh
+      FileUtils.mkdir_p '/tmp/fzf-zsh'
+      FileUtils.cp File.expand_path('~/.fzf.zsh'), '/tmp/fzf-zsh/.zshrc'
+      'PS1= PROMPT_COMMAND= HISTSIZE=100 ZDOTDIR=/tmp/fzf-zsh zsh'
+    end
+  end
+end
+
 class Tmux
   include Temp
 
@@ -37,18 +60,33 @@ class Tmux
 
   attr_reader :win
 
-  def initialize shell = 'bash'
-    @win = go("new-window -d -P -F '#I' 'PS1= PROMPT_COMMAND= bash --rcfile ~/.fzf.#{shell}'").first
+  def initialize shell = :bash
+    @win =
+      case shell
+      when :bash
+        go("new-window -d -P -F '#I' '#{Shell.bash}'").first
+      when :zsh
+        go("new-window -d -P -F '#I' '#{Shell.zsh}'").first
+      when :fish
+        go("new-window -d -P -F '#I' 'fish'").first
+      else
+        raise "Unknown shell: #{shell}"
+      end
     @lines = `tput lines`.chomp.to_i
+
+    if shell == :fish
+      send_keys('function fish_prompt; end; clear', :Enter)
+      self.until { |lines| lines.empty? }
+    end
   end
 
   def closed?
     !go("list-window -F '#I'").include?(win)
   end
 
-  def close timeout = 1
+  def close
     send_keys 'C-c', 'C-u', 'exit', :Enter
-    wait(timeout) { closed? }
+    wait { closed? }
   end
 
   def kill
@@ -56,35 +94,68 @@ class Tmux
   end
 
   def send_keys *args
+    target =
+      if args.last.is_a?(Hash)
+        hash = args.pop
+        go("select-window -t #{win}")
+        "#{win}.#{hash[:pane]}"
+      else
+        win
+      end
     args = args.map { |a| %{"#{a}"} }.join ' '
-    go("send-keys -t #{win} #{args}")
+    go("send-keys -t #{target} #{args}")
   end
 
-  def capture
-    go("capture-pane -t #{win} \\; save-buffer #{TEMPNAME}")
-    raise "Window not found" if $?.exitstatus != 0
+  def capture opts = {}
+    timeout, pane = defaults(opts).values_at(:timeout, :pane)
+    waited = 0
+    loop do
+      go("capture-pane -t #{win}.#{pane} \\; save-buffer #{TEMPNAME}")
+      break if $?.exitstatus == 0
+
+      if waited > timeout
+        raise "Window not found"
+      end
+      waited += 0.1
+      sleep 0.1
+    end
     readonce.split($/)[0, @lines].reverse.drop_while(&:empty?).reverse
   end
 
-  def until timeout = 1
-    wait(timeout) { yield capture }
+  def until opts = {}
+    lines = nil
+    wait(opts) do
+      yield lines = capture(opts)
+    end
+    lines
   end
 
+  def prepare
+    self.send_keys 'echo hello', :Enter
+    self.until { |lines| lines[-1].start_with?('hello') }
+    self.send_keys 'clear', :Enter
+    self.until { |lines| lines.empty? }
+  end
 private
-  def wait timeout = 1
+  def defaults opts
+    { timeout: 5, pane: 0 }.merge(opts)
+  end
+
+  def wait opts = {}
+    timeout, pane = defaults(opts).values_at(:timeout, :pane)
     waited = 0
     until yield
-      waited += 0.1
-      sleep 0.1
       if waited > timeout
         hl = '=' * 10
         puts hl
-        capture.each_with_index do |line, idx|
+        capture(opts).each_with_index do |line, idx|
           puts [idx.to_s.rjust(2), line].join(': ')
         end
         puts hl
         raise "timeout"
       end
+      waited += 0.1
+      sleep 0.1
     end
   end
 
@@ -93,7 +164,7 @@ private
   end
 end
 
-class TestGoFZF < MiniTest::Unit::TestCase
+class TestBase < Minitest::Test
   include Temp
 
   FIN = 'FIN'
@@ -104,11 +175,6 @@ class TestGoFZF < MiniTest::Unit::TestCase
   def setup
     ENV.delete 'FZF_DEFAULT_OPTS'
     ENV.delete 'FZF_DEFAULT_COMMAND'
-    @tmux = Tmux.new
-  end
-
-  def teardow