Add support for search history

- Add `--history` option (e.g. fzf --history ~/.fzf.history)
- Add `--history-max` option for limiting the size of the file (default 1000)
- Add `previous-history` and `next-history` actions for `--bind`
    - CTRL-P and CTRL-N are automatically remapped to these actions when
      `--history` is used

Closes #249, #251

6 files changed, 163 insertions, 11 deletions

diff --git a/fzf b/fzf
index a29ae332..78a02fbf 100755
--- a/fzf
+++ b/fzf
@@ -206,11 +206,11 @@ class FZF
         @expect = true
       when /^--expect=(.*)$/
         @expect = true
-      when '--toggle-sort', '--tiebreak', '--color', '--bind'
+      when '--toggle-sort', '--tiebreak', '--color', '--bind', '--history', '--history-max'
         argv.shift
       when '--tac', '--no-tac', '--sync', '--no-sync', '--hscroll', '--no-hscroll',
-           '--inline-info', '--no-inline-info', /^--bind=(.*)$/,
-           /^--color=(.*)$/, /^--toggle-sort=(.*)$/, /^--tiebreak=(.*)$/
+           '--inline-info', '--no-inline-info', '--null', /^--bind=(.*)$/,
+           /^--color=(.*)$/, /^--toggle-sort=(.*)$/, /^--tiebreak=(.*)$/, /^--history(-max)?=(.*)$/
         # XXX
       else
         usage 1, "illegal option: #{o}"
diff --git a/shell/completion.bash b/shell/completion.bash
index 59bdfe46..42d66c1d 100644
--- a/shell/completion.bash
+++ b/shell/completion.bash
@@ -45,7 +45,10 @@ _fzf_opts_completion() {
     --print-query
     --expect
     --toggle-sort
-    --sync"
+    --sync
+    --null
+    --history
+    --history-max"
 
   case "${prev}" in
   --tiebreak)
@@ -56,6 +59,10 @@ _fzf_opts_completion() {
     COMPREPLY=( $(compgen -W "dark light 16 bw" -- ${cur}) )
     return 0
     ;;
+  --history)
+    COMPREPLY=()
+    return 0
+    ;;
   esac
 
   if [[ ${cur} =~ ^-|\+ ]]; then
@@ -207,7 +214,7 @@ EOF
 }
 
 # fzf options
-complete -F _fzf_opts_completion fzf
+complete -o default -F _fzf_opts_completion fzf
 
 d_cmds="cd pushd rmdir"
 f_cmds="
diff --git a/src/constants.go b/src/constants.go
index 20f4bf8c..87ba0f82 100644
--- a/src/constants.go
+++ b/src/constants.go
@@ -32,6 +32,9 @@ const (
 
 	// Not to cache mergers with large lists
 	mergerCacheMax int = 100000
+
+	// History
+	defaultHistoryMax int = 1000
 )
 
 // fzf events
diff --git a/src/options.go b/src/options.go
index b4afad76..2a041ef6 100644
--- a/src/options.go
+++ b/src/options.go
@@ -42,6 +42,8 @@ const usage = `usage: fzf [options]
         --prompt=STR      Input prompt (default: '> ')
         --toggle-sort=KEY Key to toggle sort
         --bind=KEYBINDS   Custom key bindings. Refer to the man page.
+        --history=FILE    History file
+        --history-max=N   Maximum number of history entries (default: 1000)
 
   Scripting
     -q, --query=STR       Start the finder with the given query
@@ -118,6 +120,7 @@ type Options struct {
 	PrintQuery bool
 	ReadZero   bool
 	Sync       bool
+	History    *History
 	Version    bool
 }
 
@@ -157,6 +160,7 @@ func defaultOptions() *Options {
 		PrintQuery: false,
 		ReadZero:   false,
 		Sync:       false,
+		History:    nil,
 		Version:    false}
 }
 
@@ -196,6 +200,23 @@ func optionalNextString(args []string, i *int) string {
 	return ""
 }
 
+func atoi(str string) int {
+	num, err := strconv.Atoi(str)
+	if err != nil {
+		errorExit("not a valid integer: " + str)
+	}
+	return num
+}
+
+func nextInt(args []string, i *int, message string) int {
+	if len(args) > *i+1 {
+		*i++
+	} else {
+		errorExit(message)
+	}
+	return atoi(args[*i])
+}
+
 func optionalNumeric(args []string, i *int) int {
 	if len(args) > *i+1 {
 		if strings.IndexAny(args[*i+1], "0123456789") == 0 {
@@ -424,6 +445,10 @@ func parseKeymap(keymap map[int]actionType, toggleSort bool, str string) (map[in
 			keymap[key] = actPageUp
 		case "page-down":
 			keymap[key] = actPageDown
+		case "previous-history":
+			keymap[key] = actPreviousHistory
+		case "next-history":
+			keymap[key] = actNextHistory
 		case "toggle-sort":
 			keymap[key] = actToggleSort
 			toggleSort = true
@@ -444,6 +469,29 @@ func checkToggleSort(keymap map[int]actionType, str string) map[int]actionType {
 }
 
 func parseOptions(opts *Options, allArgs []string) {
+	keymap := make(map[int]actionType)
+	var historyMax int
+	if opts.History == nil {
+		historyMax = defaultHistoryMax
+	} else {
+		historyMax = opts.History.maxSize
+	}
+	setHistory := func(path string) {
+		h, e := NewHistory(path, historyMax)
+		if e != nil {
+			errorExit(e.Error())
+		}
+		opts.History = h
+	}
+	setHistoryMax := func(max int) {
+		historyMax = max
+		if historyMax < 1 {
+			errorExit("history max must be a positive integer")
+		}
+		if opts.History != nil {
+			opts.History.maxSize = historyMax
+		}
+	}
 	for i := 0; i < len(allArgs); i++ {
 		arg := allArgs[i]
 		switch arg {
@@ -465,7 +513,7 @@ func parseOptions(opts *Options, allArgs []string) {
 		case "--tiebreak":
 			opts.Tiebreak = parseTiebreak(nextString(allArgs, &i, "sort criterion required"))
 		case "--bind":
-			opts.Keymap, opts.ToggleSort = parseKeymap(opts.Keymap, opts.ToggleSort, nextString(allArgs, &i, "bind expression required"))
+			keymap, opts.ToggleSort = parseKeymap(keymap, opts.ToggleSort, nextString(allArgs, &i, "bind expression required"))
 		case "--color":
 			spec := optionalNextString(allArgs, &i)
 			if len(spec) == 0 {
@@ -474,7 +522,7 @@ func parseOptions(opts *Options, allArgs []string) {
 				opts.Theme = parseTheme(opts.Theme, spec)
 			}
 		case "--toggle-sort":
-			opts.Keymap = checkToggleSort(opts.Keymap, nextString(allArgs, &i, "key name required"))
+			keymap = checkToggleSort(keymap, nextString(allArgs, &i, "key name required"))
 			opts.ToggleSort = true
 		case "-d", "--delimiter":
 			opts.Delimiter = delimiterRegexp(nextString(allArgs, &i, "delimiter required"))
@@ -546,6 +594,12 @@ func parseOptions(opts *Options, allArgs []string) {
 			opts.Sync = false
 		case "--async":
 			opts.Sync = false
+		case "--no-history":
+			opts.History = nil
+		case "--history":
+			setHistory(nextString(allArgs, &i, "history file path required"))
+		case "--history-max":
+			setHistoryMax(nextInt(allArgs, &i, "history max size required"))
 		case "--version":
 			opts.Version = true
 		default:
@@ -564,7 +618,7 @@ func parseOptions(opts *Options, allArgs []string) {
 			} else if match, _ := optString(arg, "-s|--sort="); match {
 				opts.Sort = 1 // Don't care
 			} else if match, value := optString(arg, "--toggle-sort="); match {
-				opts.Keymap = checkToggleSort(opts.Keymap, value)
+				keymap = checkToggleSort(keymap, value)
 				opts.ToggleSort = true
 			} else if match, value := optString(arg, "--expect="); match {
 				opts.Expect = parseKeyChords(value, "key names required")
@@ -573,13 +627,32 @@ func parseOptions(opts *Options, allArgs []string) {
 			} else if match, value := optString(arg, "--color="); match {
 				opts.Theme = parseTheme(opts.Theme, value)
 			} else if match, value := optString(arg, "--bind="); match {
-				opts.Keymap, opts.ToggleSort = parseKeymap(opts.Keymap, opts.ToggleSort, value)
+				keymap, opts.ToggleSort = parseKeymap(keymap, opts.ToggleSort, value)
+			} else if match, value := optString(arg, "--history="); match {
+				setHistory(value)
+			} else if match, value := optString(arg, "--history-max="); match {
+				setHistoryMax(atoi(value))
 			} else {
 				errorExit("unknown option: " + arg)
 			}
 		}
 	}
 
+	// Change default actions for CTRL-N / CTRL-P when --history is used
+	if opts.History != nil {
+		if _, prs := keymap[curses.CtrlP]; !prs {
+			keymap[curses.CtrlP] = actPreviousHistory
+		}
+		if _, prs := keymap[curses.CtrlN]; !prs {
+			keymap[curses.CtrlN] = actNextHistory
+		}
+	}
+
+	// Override default key bindings
+	for key, act := range keymap {
+		opts.Keymap[key] = act
+	}
+
 	// If we're not using extended search mode, --nth option becomes irrelevant
 	// if it contains the whole range
 	if opts.Mode == ModeFuzzy || len(opts.Nth) == 1 {
diff --git a/src/terminal.go b/src/terminal.go
index d27c0d60..4ff26591 100644
--- a/src/terminal.go
+++ b/src/terminal.go
@@ -36,6 +36,7 @@ type Terminal struct {
 	keymap     map[int]actionType
 	pressed    int
 	printQuery bool
+	history    *History
 	count      int
 	progress   int
 	reading    bool
@@ -116,6 +117,8 @@ const (
 	actPageUp
 	actPageDown
 	actToggleSort
+	actPreviousHistory
+	actNextHistory
 )
 
 func defaultKeymap() map[int]actionType {
@@ -186,6 +189,7 @@ func NewTerminal(opts *Options, eventBox *util.EventBox) *Terminal {
 		keymap:     opts.Keymap,
 		pressed:    0,
 		printQuery: opts.PrintQuery,
+		history:    opts.History,
 		merger:     EmptyMerger,
 		selected:   make(map[uint32]selectedItem),
 		reqBox:     util.NewEventBox(),
@@ -610,6 +614,13 @@ func (t *Terminal) Loop() {
 		}()
 	}
 
+	exit := func(code int) {
+		if code == 0 && t.history != nil {
+			t.history.append(string(t.input))
+		}
+		os.Exit(code)
+	}
+
 	go func() {
 		for {
 			t.reqBox.Wait(func(events *util.Events) {
@@ -636,10 +647,10 @@ func (t *Terminal) Loop() {
 					case reqClose:
 						C.Close()
 						t.output()
-						os.Exit(0)
+						exit(0)
 					case reqQuit:
 						C.Close()
-						os.Exit(1)
+						exit(1)
 					}
 				}
 				t.placeCursor()
@@ -830,6 +841,18 @@ func (t *Terminal) Loop() {
 			prefix := copySlice(t.input[:t.cx])
 			t.input = append(append(prefix, event.Char), t.input[t.cx:]...)
 			t.cx++
+		case actPreviousHistory:
+			if t.history != nil {
+				t.history.override(string(t.input))
+				t.input = []rune(t.history.previous())
+				t.cx = len(t.input)
+			}
+		case actNextHistory:
+			if t.history != nil {
+				t.history.override(string(t.input))
+				t.input = []rune(t.history.next())
+				t.cx = len(t.input)
+			}
 		case actMouse:
 			me := event.MouseEvent
 			mx, my := util.Constrain(me.X-len(t.prompt), 0, len(t.input)), me.Y
diff --git a/test/test_go.rb b/test/test_go.rb
index 32677ad5..f7267601 100644
--- a/test/test_go.rb
+++ b/test/test_go.rb
@@ -566,6 +566,52 @@ class TestGoFZF < TestBase
     assert_equal %w[2 1 10 20 30 40 50 60 70 80 90 100], readonce.split($/)
   end
 
+  def test_history
+    history_file = '/tmp/fzf-test-history'
+
+    # History with limited number of entries
+    File.unlink history_file rescue nil
+    opts = "--history=#{history_file} --history-max=4"
+    input = %w[00 11 22 33 44].map { |e| e + $/ }
+    input.each do |keys|
+      tmux.send_keys "seq 100 | #{fzf opts}", :Enter
+      tmux.until { |lines| lines[-2].include? '100/100' }
+      tmux.send_keys keys
+      tmux.until { |lines| lines[-2].include? '1/100' }
+      tmux.send_keys :Enter
+    end
+    assert_equal input[1..-1], File.readlines(history_file)
+
+    # Update history entries (not changed on disk)
+    tmux.send_keys "seq 100 | #{fzf opts}", :Enter
+    tmux.until { |lines| lines[-2].include? '100/100' }
+    tmux.send_keys 'C-p'
+    tmux.until { |lines| lines[-1].end_with? '> 44' }
+    tmux.send_keys 'C-p'
+    tmux.until { |lines| lines[-1].end_with? '> 33' }
+    tmux.send_keys :BSpace
+    tmux.until { |lines| lines[-1].end_with? '> 3' }
+    tmux.send_keys 1
+    tmux.until { |lines| lines[-1].end_with? '> 31' }
+    tmux.send_keys 'C-p'
+    tmux.until { |lines| lines[-1].end_with? '> 22' }
+    tmux.send_keys 'C-n'
+    tmux.until { |lines| lines[-1].end_with? '> 31' }
+    tmux.send_keys 0
+    tmux.until { |lines| lines[-1].end_with? '> 310' }
+    tmux.send_keys :Enter
+    assert_equal %w[22 33 44 310].map { |e| e + $/ }, File.readlines(history_file)
+
+    # Respect --bind option
+    tmux.send_keys "seq 100 | #{fzf opts + ' --bind ctrl-p:next-history,ctrl-n:previous-history'}", :Enter
+    tmux.until { |lines| lines[-2].include? '100/100' }
+    tmux.send_keys 'C-n', 'C-n', 'C-n', 'C-n', 'C-p'
+    tmux.until { |lines| lines[-1].end_with?('33') }
+    tmux.send_keys :Enter
+  ensure
+    File.unlink history_file
+  end
+
 private
   def writelines path, lines
     File.unlink path while File.exists? path