Add reverse search functionality (#958)

* Add reverse search functionality

* Change keybindings for extend to be in select mode, incorporate Movement and Direction enums

* Fix accidental revert of #948 in rebase

* Add reverse search to docs, clean up mismatched whitespace

* Reverse search optimization

* More optimization via github feedback

3 files changed, 90 insertions, 43 deletions

diff --git a/book/src/keymap.md b/book/src/keymap.md
index 6bcd09bc..5a6aee41 100644
--- a/book/src/keymap.md
+++ b/book/src/keymap.md
@@ -106,13 +106,13 @@
 
 ### Search
 
-> TODO: The search implementation isn't ideal yet -- we don't support searching in reverse.
 
 | Key   | Description                                 | Command              |
 | ----- | -----------                                 | -------              |
 | `/`   | Search for regex pattern                    | `search`             |
+| `?`   | Search for previous pattern                 | `rsearch`            |
 | `n`   | Select next search match                    | `search_next`        |
-| `N`   | Add next search match to selection          | `extend_search_next` |
+| `N`   | Select previous search match                | `search_prev`        |
 | `*`   | Use current selection as the search pattern | `search_selection`   |
 
 ### Minor modes
@@ -185,16 +185,16 @@ TODO: Mappings for selecting syntax nodes (a superset of `[`).
 
 This layer is similar to vim keybindings as kakoune does not support window.
 
-| Key           | Description             | Command           |
-| -----         | -------------           | -------           |
-| `w`, `Ctrl-w` | Switch to next window   | `rotate_view`     |
-| `v`, `Ctrl-v` | Vertical right split    | `vsplit`          |
-| `s`, `Ctrl-s` | Horizontal bottom split | `hsplit`          |
-| `h`, `Ctrl-h`, `left` | Move to left split      | `jump_view_left`  |
-| `j`, `Ctrl-j`, `down` | Move to split below     | `jump_view_down`  |
-| `k`, `Ctrl-k`, `up` | Move to split above     | `jump_view_up`    |
-| `l`, `Ctrl-l`, `right` | Move to right split     | `jump_view_right` |
-| `q`, `Ctrl-q` | Close current window    | `wclose`          |
+| Key                    | Description                    | Command           |
+| -----                  | -------------                  | -------           |
+| `w`, `Ctrl-w`          | Switch to next window          | `rotate_view`     |
+| `v`, `Ctrl-v`          | Vertical right split           | `vsplit`          |
+| `s`, `Ctrl-s`          | Horizontal bottom split        | `hsplit`          |
+| `h`, `Ctrl-h`, `left`  | Move to left split             | `jump_view_left`  |
+| `j`, `Ctrl-j`, `down`  | Move to split below            | `jump_view_down`  |
+| `k`, `Ctrl-k`, `up`    | Move to split above            | `jump_view_up`    |
+| `l`, `Ctrl-l`, `right` | Move to right split            | `jump_view_right` |
+| `q`, `Ctrl-q`          | Close current window           | `wclose`          |
 
 #### Space mode
 
@@ -222,12 +222,12 @@ This layer is a kludge of mappings, mostly pickers.
 
 Mappings in the style of [vim-unimpaired](https://github.com/tpope/vim-unimpaired).
 
-| Key       | Description                        | Command           |
-| -----     | -----------                        | -------           |
-| `[d`      | Go to previous diagnostic          | `goto_prev_diag`  |
-| `]d`      | Go to next diagnostic              | `goto_next_diag`  |
-| `[D`      | Go to first diagnostic in document | `goto_first_diag` |
-| `]D`      | Go to last diagnostic in document  | `goto_last_diag`  |
+| Key       | Description                        | Command             |
+| -----     | -----------                        | -------             |
+| `[d`      | Go to previous diagnostic          | `goto_prev_diag`    |
+| `]d`      | Go to next diagnostic              | `goto_next_diag`    |
+| `[D`      | Go to first diagnostic in document | `goto_first_diag`   |
+| `]D`      | Go to last diagnostic in document  | `goto_last_diag`    |
 | `[space`  | Add newline above                  | `add_newline_above` |
 | `]space`  | Add newline below                  | `add_newline_below` |
 
diff --git a/helix-term/src/commands.rs b/helix-term/src/commands.rs
index 3d134ce5..c8f64531 100644
--- a/helix-term/src/commands.rs
+++ b/helix-term/src/commands.rs
@@ -217,8 +217,11 @@ impl Command {
         split_selection, "Split selection into subselections on regex matches",
         split_selection_on_newline, "Split selection on newlines",
         search, "Search for regex pattern",
+        rsearch, "Reverse search for regex pattern",
         search_next, "Select next search match",
+        search_prev, "Select previous search match",
         extend_search_next, "Add next search match to selection",
+        extend_search_prev, "Add previous search match to selection",
         search_selection, "Use current selection as search pattern",
         global_search, "Global Search in workspace folder",
         extend_line, "Select current line, if already selected, extend to next line",
@@ -1170,38 +1173,62 @@ fn split_selection_on_newline(cx: &mut Context) {
     doc.set_selection(view.id, selection);
 }
 
-fn search_impl(doc: &mut Document, view: &mut View, contents: &str, regex: &Regex, extend: bool) {
+fn search_impl(
+    doc: &mut Document,
+    view: &mut View,
+    contents: &str,
+    regex: &Regex,
+    movement: Movement,
+    direction: Direction,
+) {
     let text = doc.text().slice(..);
     let selection = doc.selection(view.id);
 
-    // Get the right side of the primary block cursor.
-    let start = text.char_to_byte(graphemes::next_grapheme_boundary(
-        text,
-        selection.primary().cursor(text),
-    ));
+    // Get the right side of the primary block cursor for forward search, or the
+    //grapheme before the start of the selection for reverse search.
+    let start = match direction {
+        Direction::Forward => text.char_to_byte(graphemes::next_grapheme_boundary(
+            text,
+            selection.primary().to(),
+        )),
+        Direction::Backward => text.char_to_byte(graphemes::prev_grapheme_boundary(
+            text,
+            selection.primary().from(),
+        )),
+    };
+
+    //A regex::Match returns byte-positions in the str. In the case where we
+    //do a reverse search and wraparound to the end, we don't need to search
+    //the text before the current cursor position for matches, but by slicing
+    //it out, we need to add it back to the position of the selection.
+    let mut offset = 0;
 
     // use find_at to find the next match after the cursor, loop around the end
     // Careful, `Regex` uses `bytes` as offsets, not character indices!
-    let mat = regex
-        .find_at(contents, start)
-        .or_else(|| regex.find(contents));
+    let mat = match direction {
+        Direction::Forward => regex
+            .find_at(contents, start)
+            .or_else(|| regex.find(contents)),
+        Direction::Backward => regex.find_iter(&contents[..start]).last().or_else(|| {
+            offset = start;
+            regex.find_iter(&contents[start..]).last()
+        }),
+    };
     // TODO: message on wraparound
     if let Some(mat) = mat {
-        let start = text.byte_to_char(mat.start());
-        let end = text.byte_to_char(mat.end());
+        let start = text.byte_to_char(mat.start() + offset);
+        let end = text.byte_to_char(mat.end() + offset);
 
         if end == 0 {
             // skip empty matches that don't make sense
             return;
         }
-
-        let selection = if extend {
-            selection.clone().push(Range::new(start, end))
-        } else {
-            selection
+        let selection = match movement {
+            Movement::Extend => selection.clone().push(Range::new(start, end)),
+            Movement::Move => selection
                 .clone()
                 .remove(selection.primary_index())
-                .push(Range::new(start, end))
+                .push(Range::new(start, end)),
         };
 
         doc.set_selection(view.id, selection);
@@ -1220,6 +1247,14 @@ fn search_completions(cx: &mut Context, reg: Option<char>) -> Vec<String> {
 
 // TODO: use one function for search vs extend
 fn search(cx: &mut Context) {
+    searcher(cx, Direction::Forward)
+}
+
+fn rsearch(cx: &mut Context) {
+    searcher(cx, Direction::Backward)
+}
+// TODO: use one function for search vs extend
+fn searcher(cx: &mut Context, direction: Direction) {
     let reg = cx.register.unwrap_or('/');
     let (_, doc) = current!(cx.editor);
 
@@ -1245,14 +1280,14 @@ fn search(cx: &mut Context) {
             if event != PromptEvent::Update {
                 return;
             }
-            search_impl(doc, view, &contents, &regex, false);
+            search_impl(doc, view, &contents, &regex, Movement::Move, direction);
         },
     );
 
     cx.push_layer(Box::new(prompt));
 }
 
-fn search_next_impl(cx: &mut Context, extend: bool) {
+fn search_next_or_prev_impl(cx: &mut Context, movement: Movement, direction: Direction) {
     let (view, doc) = current!(cx.editor);
     let registers = &cx.editor.registers;
     if let Some(query) = registers.read('/') {
@@ -1267,7 +1302,7 @@ fn search_next_impl(cx: &mut Context, extend: bool) {
             .case_insensitive(case_insensitive)
             .build()
         {
-            search_impl(doc, view, &contents, &regex, extend);
+            search_impl(doc, view, &contents, &regex, movement, direction);
         } else {
             // get around warning `mutable_borrow_reservation_conflict`
             // which will be a hard error in the future
@@ -1279,11 +1314,18 @@ fn search_next_impl(cx: &mut Context, extend: bool) {
 }
 
 fn search_next(cx: &mut Context) {
-    search_next_impl(cx, false);
+    search_next_or_prev_impl(cx, Movement::Move, Direction::Forward);
 }
 
+fn search_prev(cx: &mut Context) {
+    search_next_or_prev_impl(cx, Movement::Move, Direction::Backward);
+}
 fn extend_search_next(cx: &mut Context) {
-    search_next_impl(cx, true);
+    search_next_or_prev_impl(cx, Movement::Extend, Direction::Forward);
+}
+
+fn extend_search_prev(cx: &mut Context) {
+    search_next_or_prev_impl(cx, Movement::Extend, Direction::Backward);
 }
 
 fn search_selection(cx: &mut Context) {
diff --git a/helix-term/src/keymap.rs b/helix-term/src/keymap.rs
index b48eea14..c85a9c3f 100644
--- a/helix-term/src/keymap.rs
+++ b/helix-term/src/keymap.rs
@@ -504,10 +504,9 @@ impl Default for Keymaps {
             },
 
             "/" => search,
-            // ? for search_reverse
+            "?" => rsearch,
             "n" => search_next,
-            "N" => extend_search_next,
-            // N for search_prev
+            "N" => search_prev,
             "*" => search_selection,
 
             "u" => undo,
@@ -633,11 +632,17 @@ impl Default for Keymaps {
             "B" => extend_prev_long_word_start,
             "E" => extend_next_long_word_end,
 
+            "n" => extend_search_next,
+            "N" => extend_search_prev,
+
             "t" => extend_till_char,
             "f" => extend_next_char,
             "T" => extend_till_prev_char,
             "F" => extend_prev_char,
 
+            "n" => extend_search_next,
+            "N" => extend_search_prev,
+
             "home" => extend_to_line_start,
             "end" => extend_to_line_end,
             "esc" => exit_select_mode,