Add --tac option and reverse display order of --no-sort

DISCLAIMER: This is a backward incompatible change

9 files changed, 79 insertions, 50 deletions

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..ec4c5e8d 100644
--- a/src/core.go
+++ b/src/core.go
@@ -93,7 +93,7 @@ func Run(options *Options) {
 		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 {
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/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)
 					}
 				}