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

3 files changed, 105 insertions, 6 deletions

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