Hecto, Chapter 6: Search

Hecto, Chapter 6: Search

November 8, 2019

Previous chapter - Overview - Appendices - Next Chapter

Our text editor is done - we can open, edit and save files. The upcoming two features add more functionality to it. In this chapter, we will implement a minimal search feature.

For that, we reuse prompt(). When the user types a search query and presses Enter, we’ll loop through all the rows of our file, and if a row contains their query string, we’ll move the cursor to match. For that, we are going to need a method which searchs a single Row and returns the position of the match. Let’s start with that now.

src/document.rs CHANGED
@@ -94,4 +94,12 @@ impl Document {
94
94
  pub fn is_dirty(&self) -> bool {
95
95
  self.dirty
96
96
  }
97
+ pub fn find(&self, query: &str) -> Option<Position> {
98
+ for (y, row) in self.rows.iter().enumerate() {
99
+ if let Some(x) = row.find(query) {
100
+ return Some(Position { x, y });
101
+ }
102
+ }
103
+ None
104
+ }
97
105
  }
src/editor.rs CHANGED
@@ -57,7 +57,8 @@ impl Editor {
57
57
  }
58
58
  pub fn default() -> Self {
59
59
  let args: Vec<String> = env::args().collect();
60
- let mut initial_status = String::from("HELP: Ctrl-S = save | Ctrl-Q = quit");
60
+ let mut initial_status =
61
+ String::from("HELP: Ctrl-F = find | Ctrl-S = save | Ctrl-Q = quit");
61
62
 
62
63
  let document = if let Some(file_name) = args.get(1) {
63
64
  let doc = Document::open(file_name);
@@ -131,6 +132,15 @@ impl Editor {
131
132
  self.should_quit = true
132
133
  }
133
134
  Key::Ctrl('s') => self.save(),
135
+ Key::Ctrl('f') => {
136
+ if let Some(query) = self.prompt("Search: ").unwrap_or(None) {
137
+ if let Some(position) = self.document.find(&query[..]) {
138
+ self.cursor_position = position;
139
+ } else {
140
+ self.status_message = StatusMessage::from(format!("Not found :{}.", query));
141
+ }
142
+ }
143
+ }
134
144
  Key::Char(c) => {
135
145
  self.document.insert(&self.cursor_position, c);
136
146
  self.move_cursor(Key::Right);
src/row.rs CHANGED
@@ -104,4 +104,17 @@ impl Row {
104
104
  pub fn as_bytes(&self) -> &[u8] {
105
105
  self.string.as_bytes()
106
106
  }
107
+ pub fn find(&self, query: &str) -> Option<usize> {
108
+ let matching_byte_index = self.string.find(query);
109
+ if let Some(matching_byte_index) = matching_byte_index {
110
+ for (grapheme_index, (byte_index, _)) in
111
+ self.string[..].grapheme_indices(true).enumerate()
112
+ {
113
+ if matching_byte_index == byte_index {
114
+ return Some(grapheme_index);
115
+ }
116
+ }
117
+ }
118
+ None
119
+ }
107
120
  }

See this step on github

Let’s go through this change starting at Row. We have added a function which returns an Option, which contains either the x position of the match or None. We then use the find method of String to retrieve the byte index of the match. Remember that this might not be the same as the index of the grapheme! To convert the byte index into the grapheme index, we use a slightly convoluted loop. Let’s unravel that one.

grapheme_indices() returns an iterator over a pair of (byte_index, grapheme) for each grapheme in the string. enumerate() enumerates the iterator, so it gives us the grapheme index of each entry of the iterator.

We take this to our advantage and use the iterator until we arrive at the grapheme with the same byte index as our match, and return the corresponding grapheme index.

In Document, we try to return a Position of the match within the full document, if there is any. We do this by iterating over all rows and performing match on each row, until we have a match. We then return the current row index and the index of the match as the position of the match within the document.

In Editor, we use a very similar logic as before around prompt. We retrieve the search query from the user and pass it to find. If we find a match, we move our cursor. If we don’t, we display a message to the user.

Last but not least, we also modify our initial welcome message for the user, so that they know how to use our new search functionality.

Now, let’s make our search feature fancy. We want to support incremental search, meaning the file is searched after each keypress when the user is typing in their search query.

To implement this, we’re going to get prompt to take a callback function as an argument. We’ll have to call this function after each keypress, passing the current search query inputted by the user and the last key they pressed. I’ll explain the concept in a bit.

src/editor.rs CHANGED
@@ -103,7 +103,7 @@ impl Editor {
103
103
  }
104
104
  fn save(&mut self) {
105
105
  if self.document.file_name.is_none() {
106
- let new_name = self.prompt("Save as: ").unwrap_or(None);
106
+ let new_name = self.prompt("Save as: ", |_, _, _| {}).unwrap_or(None);
107
107
  if new_name.is_none() {
108
108
  self.status_message = StatusMessage::from("Save aborted.".to_string());
109
109
  return;
@@ -133,7 +133,15 @@ impl Editor {
133
133
  }
134
134
  Key::Ctrl('s') => self.save(),
135
135
  Key::Ctrl('f') => {
136
- if let Some(query) = self.prompt("Search: ").unwrap_or(None) {
136
+ if let Some(query) = self
137
+ .prompt("Search: ", |editor, _, query| {
138
+ if let Some(position) = editor.document.find(&query) {
139
+ editor.cursor_position = position;
140
+ editor.scroll();
141
+ }
142
+ })
143
+ .unwrap_or(None)
144
+ {
137
145
  if let Some(position) = self.document.find(&query[..]) {
138
146
  self.cursor_position = position;
139
147
  } else {
@@ -331,12 +339,16 @@ impl Editor {
331
339
  print!("{}", text);
332
340
  }
333
341
  }
334
- fn prompt(&mut self, prompt: &str) -> Result<Option<String>, std::io::Error> {
342
+ fn prompt<C>(&mut self, prompt: &str, callback: C) -> Result<Option<String>, std::io::Error>
343
+ where
344
+ C: Fn(&mut Self, Key, &String),
345
+ {
335
346
  let mut result = String::new();
336
347
  loop {
337
348
  self.status_message = StatusMessage::from(format!("{}{}", prompt, result));
338
349
  self.refresh_screen()?;
339
- match Terminal::read_key()? {
350
+ let key = Terminal::read_key()?;
351
+ match key {
340
352
  Key::Backspace => result.truncate(result.len().saturating_sub(1)),
341
353
  Key::Char('\n') => break,
342
354
  Key::Char(c) => {
@@ -350,6 +362,7 @@ impl Editor {
350
362
  }
351
363
  _ => (),
352
364
  }
365
+ callback(self, key, &result);
353
366
  }
354
367
  self.status_message = StatusMessage::from(String::new());
355
368
  if result.is_empty() {

See this step on github

We are using a new concept here called closures. It comes with a new bit of syntax, which makes this code a bit hard to read.

Let’s start with the concept. What we want is to pass a function to prompt, and we want this function to be called every time the user has modified his query. We want this so that we can perform a search on the partial query while the user is typing.

How do we do that? First, we need to modify the signature for prompt. It now looks like this:

 fn prompt<C>(&mut self, prompt: &str, callback: C) -> Result<Option<String>, std::io::Error> where C: Fn(&mut Self, Key, &String) {
     //...
 }

The initial <C> comes from the concept of Traits. We won’t be implementing any complex traits in the scope of this tutorial, so you won’t be seeing this syntax anywhere else. Essentially, the C is a placeholder for the callback, and you can see it repeated as the type for the paramter callback. Another new thing is the where at the end of the method definition, and this is where we define what kind of function C should be. It should essentially take three parameters: The Editor, the Key which has been pressed (we ignore it for now, but we are going to use it later), and a &String, which will be the (partial) search query. We can see callback being called with these parameters after the user has pressed a key.

How do we define a callback? Well, we can see the easiest case in the prompt for save: |_, _, _| {}. This is a closure which takes three parameters, ignores all of them and does nothing.

A more meaningful example is the addition to our Search-Prompt: Here, the closure takes three parameters (ignoring the middle parameter) and actually does something. As it’s called with every partial query, we are performing a search and setting the cursor with every key press.

Maybe you are familiar with closures in other languages, and you might ask yourself: Can’t we just access self directly within the closure, instead of passing it to prompt and then to the callback?

Well, yes and no. Yes, because a major feature of closures is that they allow you to access variables from outside of the closure definition, but no, because that does not work in this case.

The reason is that prompt takes a mutable reference to self, as it sets the status message, and it would also pass a mutable reference to callback. That is not allowed.

That’s all there is to it. We now have incremental search.

If the user cancels his search, we want to reset the cursor to the old position. For that, we are going to save the position before we start the prompt, and we check the return value. If it’s `None´, the user has cancelled his query, and we want to restore his old cursor position and scroll to it.

src/editor.rs CHANGED
@@ -12,7 +12,7 @@ const STATUS_BG_COLOR: color::Rgb = color::Rgb(239, 239, 239);
12
12
  const VERSION: &str = env!("CARGO_PKG_VERSION");
13
13
  const QUIT_TIMES: u8 = 3;
14
14
 
15
- #[derive(Default)]
15
+ #[derive(Default, Clone)]
16
16
  pub struct Position {
17
17
  pub x: usize,
18
18
  pub y: usize,
@@ -117,6 +117,27 @@ impl Editor {
117
117
  self.status_message = StatusMessage::from("Error writing file!".to_string());
118
118
  }
119
119
  }
120
+ fn search(&mut self) {
121
+ let old_position = self.cursor_position.clone();
122
+ if let Some(query) = self
123
+ .prompt("Search: ", |editor, _, query| {
124
+ if let Some(position) = editor.document.find(&query) {
125
+ editor.cursor_position = position;
126
+ editor.scroll();
127
+ }
128
+ })
129
+ .unwrap_or(None)
130
+ {
131
+ if let Some(position) = self.document.find(&query[..]) {
132
+ self.cursor_position = position;
133
+ } else {
134
+ self.status_message = StatusMessage::from(format!("Not found :{}.", query));
135
+ }
136
+ } else {
137
+ self.cursor_position = old_position;
138
+ self.scroll();
139
+ }
140
+ }
120
141
  fn process_keypress(&mut self) -> Result<(), std::io::Error> {
121
142
  let pressed_key = Terminal::read_key()?;
122
143
  match pressed_key {
@@ -132,23 +153,7 @@ impl Editor {
132
153
  self.should_quit = true
133
154
  }
134
155
  Key::Ctrl('s') => self.save(),
135
- Key::Ctrl('f') => {
156
+ Key::Ctrl('f') => self.search(),
136
- if let Some(query) = self
137
- .prompt("Search: ", |editor, _, query| {
138
- if let Some(position) = editor.document.find(&query) {
139
- editor.cursor_position = position;
140
- editor.scroll();
141
- }
142
- })
143
- .unwrap_or(None)
144
- {
145
- if let Some(position) = self.document.find(&query[..]) {
146
- self.cursor_position = position;
147
- } else {
148
- self.status_message = StatusMessage::from(format!("Not found :{}.", query));
149
- }
150
- }
151
- }
152
157
  Key::Char(c) => {
153
158
  self.document.insert(&self.cursor_position, c);
154
159
  self.move_cursor(Key::Right);

See this step on github

To clone the old position, we derive the Clone trait. This allows us to clone all values of the Position struct by calling clone.

Search forward and backward

The last feature we’d like to add is to allow th euser to advance to the next or previous match in the file using the arrow keys. The and keys will go to the previous match, and the and keys will go to the next match.

src/document.rs CHANGED
@@ -94,11 +94,13 @@ impl Document {
94
94
  pub fn is_dirty(&self) -> bool {
95
95
  self.dirty
96
96
  }
97
- pub fn find(&self, query: &str) -> Option<Position> {
98
- for (y, row) in self.rows.iter().enumerate() {
99
- if let Some(x) = row.find(query) {
97
+ pub fn find(&self, query: &str, after: &Position) -> Option<Position> {
98
+ let mut x = after.x;
99
+ for (y, row) in self.rows.iter().enumerate().skip(after.y) {
100
+ if let Some(x) = row.find(query, x) {
100
101
  return Some(Position { x, y });
101
102
  }
103
+ x = 0;
102
104
  }
103
105
  None
104
106
  }
src/editor.rs CHANGED
@@ -120,15 +120,28 @@ impl Editor {
120
120
  fn search(&mut self) {
121
121
  let old_position = self.cursor_position.clone();
122
122
  if let Some(query) = self
123
- .prompt("Search: ", |editor, _, query| {
124
- if let Some(position) = editor.document.find(&query) {
125
- editor.cursor_position = position;
126
- editor.scroll();
127
- }
128
- })
123
+ .prompt(
124
+ "Search (ESC to cancel, Arrows to navigate): ",
125
+ |editor, key, query| {
126
+ let mut moved = false;
127
+ match key {
128
+ Key::Right | Key::Down => {
129
+ editor.move_cursor(Key::Right);
130
+ moved = true;
131
+ }
132
+ _ => (),
133
+ }
134
+ if let Some(position) = editor.document.find(&query, &editor.cursor_position) {
135
+ editor.cursor_position = position;
136
+ editor.scroll();
137
+ } else if moved {
138
+ editor.move_cursor(Key::Left);
139
+ }
140
+ },
141
+ )
129
142
  .unwrap_or(None)
130
143
  {
131
- if let Some(position) = self.document.find(&query[..]) {
144
+ if let Some(position) = self.document.find(&query[..], &old_position) {
132
145
  self.cursor_position = position;
133
146
  } else {
134
147
  self.status_message = StatusMessage::from(format!("Not found :{}.", query));
src/row.rs CHANGED
@@ -104,14 +104,16 @@ impl Row {
104
104
  pub fn as_bytes(&self) -> &[u8] {
105
105
  self.string.as_bytes()
106
106
  }
107
- pub fn find(&self, query: &str) -> Option<usize> {
108
- let matching_byte_index = self.string.find(query);
107
+ pub fn find(&self, query: &str, after: usize) -> Option<usize> {
108
+ let substring: String = self.string[..].graphemes(true).skip(after).collect();
109
+ let matching_byte_index = substring.find(query);
109
110
  if let Some(matching_byte_index) = matching_byte_index {
110
111
  for (grapheme_index, (byte_index, _)) in
111
- self.string[..].grapheme_indices(true).enumerate()
112
+ substring[..].grapheme_indices(true).enumerate()
112
113
  {
113
114
  if matching_byte_index == byte_index {
114
- return Some(grapheme_index);
115
+ #[allow(clippy::integer_arithmetic)]
116
+ return Some(after + grapheme_index);
115
117
  }
116
118
  }
117
119
  }

See this step on github

We start by accepting a start position in our find methods, indicating that we want to search the next match after that position. For row, this means that we skip everything in the string up until after before performing find. We need to add after to the grapheme index of the match, since the grapheme index indicates the position in the substring without the first part of the string.

In Document, we are now skipping the first y rows when performing the search. We then try to find a match in the current row with the current x position. If we can’t find anything, we proceed to the next line, but we set x to 0 there, to make sure we start looking from the start of the next row.

We have adjusted our error message and are calling find now with the cursor position. We are also now using the formerly unused key parameter of our closure and match against the user input. If the user presses down or right, we are moving the cursor to the right as well before continuing the search with the updated parameter. Why? Because if our cursor is already at the position of a search match, we don’t want the current position to be returned to us, so we start one step to the left of the current position. In case our find did not return a match, we want the cursor to stay on its previous position. So we track if we have moved the cursor in moved and move it back in case there is no result.

Searching backwards

Now let’s take a look at searching backwards.

src/document.rs CHANGED
@@ -1,5 +1,6 @@
1
1
  use crate::Position;
2
2
  use crate::Row;
3
+ use crate::SearchDirection;
3
4
  use std::fs;
4
5
  use std::io::{Error, Write};
5
6
 
@@ -94,13 +95,39 @@ impl Document {
94
95
  pub fn is_dirty(&self) -> bool {
95
96
  self.dirty
96
97
  }
97
- pub fn find(&self, query: &str, after: &Position) -> Option<Position> {
98
- let mut x = after.x;
99
- for (y, row) in self.rows.iter().enumerate().skip(after.y) {
100
- if let Some(x) = row.find(query, x) {
101
- return Some(Position { x, y });
98
+ #[allow(clippy::indexing_slicing)]
99
+ pub fn find(&self, query: &str, at: &Position, direction: SearchDirection) -> Option<Position> {
100
+ if at.y >= self.rows.len() {
101
+ return None;
102
+ }
103
+ let mut position = Position { x: at.x, y: at.y };
104
+
105
+ let start = if direction == SearchDirection::Forward {
106
+ at.y
107
+ } else {
108
+ 0
109
+ };
110
+ let end = if direction == SearchDirection::Forward {
111
+ self.rows.len()
112
+ } else {
113
+ at.y.saturating_add(1)
114
+ };
115
+ for _ in start..end {
116
+ if let Some(row) = self.rows.get(position.y) {
117
+ if let Some(x) = row.find(&query, position.x, direction) {
118
+ position.x = x;
119
+ return Some(position);
120
+ }
121
+ if direction == SearchDirection::Forward {
122
+ position.y = position.y.saturating_add(1);
123
+ position.x = 0;
124
+ } else {
125
+ position.y = position.y.saturating_sub(1);
126
+ position.x = self.rows[position.y].len();
127
+ }
128
+ } else {
129
+ return None;
102
130
  }
103
- x = 0;
104
131
  }
105
132
  None
106
133
  }
src/editor.rs CHANGED
@@ -12,6 +12,12 @@ const STATUS_BG_COLOR: color::Rgb = color::Rgb(239, 239, 239);
12
12
  const VERSION: &str = env!("CARGO_PKG_VERSION");
13
13
  const QUIT_TIMES: u8 = 3;
14
14
 
15
+ #[derive(PartialEq, Copy, Clone)]
16
+ pub enum SearchDirection {
17
+ Forward,
18
+ Backward,
19
+ }
20
+
15
21
  #[derive(Default, Clone)]
16
22
  pub struct Position {
17
23
  pub x: usize,
@@ -119,19 +125,26 @@ impl Editor {
119
125
  }
120
126
  fn search(&mut self) {
121
127
  let old_position = self.cursor_position.clone();
122
- if let Some(query) = self
128
+ let mut direction = SearchDirection::Forward;
129
+ let query = self
123
130
  .prompt(
124
131
  "Search (ESC to cancel, Arrows to navigate): ",
125
132
  |editor, key, query| {
126
133
  let mut moved = false;
127
134
  match key {
128
135
  Key::Right | Key::Down => {
136
+ direction = SearchDirection::Forward;
129
137
  editor.move_cursor(Key::Right);
130
138
  moved = true;
131
139
  }
132
- _ => (),
140
+ Key::Left | Key::Up => direction = SearchDirection::Backward,
141
+ _ => direction = SearchDirection::Forward,
133
142
  }
134
- if let Some(position) = editor.document.find(&query, &editor.cursor_position) {
143
+ if let Some(position) =
144
+ editor
145
+ .document
146
+ .find(&query, &editor.cursor_position, direction)
147
+ {
135
148
  editor.cursor_position = position;
136
149
  editor.scroll();
137
150
  } else if moved {
@@ -139,14 +152,9 @@ impl Editor {
139
152
  }
140
153
  },
141
154
  )
142
- .unwrap_or(None)
143
- {
144
- if let Some(position) = self.document.find(&query[..], &old_position) {
155
+ .unwrap_or(None);
156
+
157
+ if query.is_none() {
145
- self.cursor_position = position;
146
- } else {
147
- self.status_message = StatusMessage::from(format!("Not found :{}.", query));
148
- }
149
- } else {
150
158
  self.cursor_position = old_position;
151
159
  self.scroll();
152
160
  }
@@ -357,9 +365,9 @@ impl Editor {
357
365
  print!("{}", text);
358
366
  }
359
367
  }
360
- fn prompt<C>(&mut self, prompt: &str, callback: C) -> Result<Option<String>, std::io::Error>
368
+ fn prompt<C>(&mut self, prompt: &str, mut callback: C) -> Result<Option<String>, std::io::Error>
361
369
  where
362
- C: Fn(&mut Self, Key, &String),
370
+ C: FnMut(&mut Self, Key, &String),
363
371
  {
364
372
  let mut result = String::new();
365
373
  loop {
src/main.rs CHANGED
@@ -14,6 +14,7 @@ mod terminal;
14
14
  pub use document::Document;
15
15
  use editor::Editor;
16
16
  pub use editor::Position;
17
+ pub use editor::SearchDirection;
17
18
  pub use row::Row;
18
19
  pub use terminal::Terminal;
19
20
 
src/row.rs CHANGED
@@ -1,3 +1,4 @@
1
+ use crate::SearchDirection;
1
2
  use std::cmp;
2
3
  use unicode_segmentation::UnicodeSegmentation;
3
4
 
@@ -104,16 +105,38 @@ impl Row {
104
105
  pub fn as_bytes(&self) -> &[u8] {
105
106
  self.string.as_bytes()
106
107
  }
107
- pub fn find(&self, query: &str, after: usize) -> Option<usize> {
108
- let substring: String = self.string[..].graphemes(true).skip(after).collect();
109
- let matching_byte_index = substring.find(query);
108
+ pub fn find(&self, query: &str, at: usize, direction: SearchDirection) -> Option<usize> {
109
+ if at > self.len {
110
+ return None;
111
+ }
112
+ let start = if direction == SearchDirection::Forward {
113
+ at
114
+ } else {
115
+ 0
116
+ };
117
+ let end = if direction == SearchDirection::Forward {
118
+ self.len
119
+ } else {
120
+ at
121
+ };
122
+ #[allow(clippy::integer_arithmetic)]
123
+ let substring: String = self.string[..]
124
+ .graphemes(true)
125
+ .skip(start)
126
+ .take(end - start)
127
+ .collect();
128
+ let matching_byte_index = if direction == SearchDirection::Forward {
129
+ substring.find(query)
130
+ } else {
131
+ substring.rfind(query)
132
+ };
110
133
  if let Some(matching_byte_index) = matching_byte_index {
111
134
  for (grapheme_index, (byte_index, _)) in
112
135
  substring[..].grapheme_indices(true).enumerate()
113
136
  {
114
137
  if matching_byte_index == byte_index {
115
138
  #[allow(clippy::integer_arithmetic)]
116
- return Some(after + grapheme_index);
139
+ return Some(start + grapheme_index);
117
140
  }
118
141
  }
119
142
  }

See this step on github

That is quite a big change for something that should just be the opposite of what we just implemented!

Let’s unravel the change step by step, starting at Row.

We have renamed after to at, since we are not necessarily looking at something after, but also before the given index. We are then calculating the size of our substring which we want to search based on the search direction: Either we want to search from the beginning to our current position, or from our current position to the end of the row. Once we have the right length, we use an iterator to collect our actual substring into a string. We allow integer arithmetics here since we have made sure that end is always bigger than or equal to start, and always smaller than or equal to the length of the current row.

You can see an enum in action: SearchDirection. We will see its definition in a bit. For now, we use it to determine whether or not we should find the first occurence in a given string, with find, or the last, with rfind. This ensures that we are finding matches in the correct direction.

In Document, we are building our own iterator, since depending on the search direction we either need to search forward or backward through the document.

We determine the range of rows through which we will be iterating based on the search direction, and then we perform the search. Same as before: If we have a match, then we can return the position we are currently on. If not, we have to set y to the next or previous row, and have to set x either to 0, in case we are searching forward, or to the length of the previous line, in case we are searching backwards.

In editor, you can see the definition of our new struct, SearchDirection. It derives Copy and Clone, which allows it to be passed around (the structure is small enough that copying it instead of passing a reference does not really matter), and PartialEq ensures that we can actually compare two search directions to one another.

Then, we are defining a new variable, direction, which we intend to set from within the prompt closure. We set the search direction to backward in case the back or left key have been pressed, and to forward on right and down. Then we pass the search direction to the adjusted find method.

Note that we also set the direction to forward again on any other keypress. If we wouldn’t do that, the search behaviour would be weird: Let’s say the cursor is on baz of foo bar baz, the user has entered b and the Search Direction is backward. If you typed a, the query would be ba and the user would jump back to bar instead of staying on baz, even though baz also matches the query.

We have also removed the final search and the “Not found” message in case the user cancels the search. We are already searching within the closure, so an additional search at the end does not bring us any benefit.

Last but not least, we needed to update the signature for our callback (and thus, for prompt), so that callback is able to modify variables accessed within it. That’s being done by changing callback to FnMut.

Congratulation, our search feature works now!

Conclusion

Since our functionality is now complete, we used this chapter again to focus a bit more on Rust topics and brushed the topic of Closures and Traits. Our editor is almost complete - in the next chapter, we are going to implement Syntax Highlighting and File Type Detection, to complete our text editor.

Twitter, Facebook