rustyline/
history.rs

1//! History API
2
3use fd_lock::RwLock;
4use log::{debug, warn};
5use std::collections::vec_deque;
6use std::collections::VecDeque;
7use std::fs::{File, OpenOptions};
8use std::io::SeekFrom;
9use std::iter::DoubleEndedIterator;
10use std::ops::Index;
11use std::path::{Path, PathBuf};
12use std::time::SystemTime;
13
14use super::Result;
15use crate::config::{Config, HistoryDuplicates};
16
17/// Search direction
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub enum SearchDirection {
20    /// Search history forward
21    Forward,
22    /// Search history backward
23    Reverse,
24}
25
26/// History search result
27#[derive(Debug, Clone, Eq, PartialEq)]
28pub struct SearchResult<'a> {
29    /// history entry
30    pub entry: &'a str,
31    /// history index
32    pub idx: usize,
33    /// match position in `entry`
34    pub pos: usize,
35}
36
37// HistoryEntry: text + timestamp
38// TODO Make possible to customize how history is stored / loaded.
39// https://github.com/kkawakam/rustyline/issues/442
40// https://github.com/kkawakam/rustyline/issues/127
41// See https://python-prompt-toolkit.readthedocs.io/en/master/pages/reference.html#prompt_toolkit.history.History abstract methods
42
43/// Current state of the history.
44#[derive(Default)]
45pub struct History {
46    entries: VecDeque<String>,
47    max_len: usize,
48    pub(crate) ignore_space: bool,
49    pub(crate) ignore_dups: bool,
50    /// Number of entries inputted by user and not saved yet
51    new_entries: usize,
52    /// last path used by either `load` or `save`
53    path_info: Option<PathInfo>,
54}
55
56/// Last histo path, modified timestamp and size
57struct PathInfo(PathBuf, SystemTime, usize);
58
59impl History {
60    // New multiline-aware history files start with `#V2\n` and have newlines
61    // and backslashes escaped in them.
62    const FILE_VERSION_V2: &'static str = "#V2";
63
64    /// Default constructor
65    #[must_use]
66    pub fn new() -> Self {
67        Self::with_config(Config::default())
68    }
69
70    /// Customized constructor with:
71    /// - `Config::max_history_size()`,
72    /// - `Config::history_ignore_space()`,
73    /// - `Config::history_duplicates()`.
74    #[must_use]
75    pub fn with_config(config: Config) -> Self {
76        Self {
77            entries: VecDeque::new(),
78            max_len: config.max_history_size(),
79            ignore_space: config.history_ignore_space(),
80            ignore_dups: config.history_duplicates() == HistoryDuplicates::IgnoreConsecutive,
81            new_entries: 0,
82            path_info: None,
83        }
84    }
85
86    /// Return the history entry at position `index`, starting from 0.
87    #[must_use]
88    pub fn get(&self, index: usize) -> Option<&String> {
89        self.entries.get(index)
90    }
91
92    /// Return the last history entry (i.e. previous command)
93    #[must_use]
94    pub fn last(&self) -> Option<&String> {
95        self.entries.back()
96    }
97
98    /// Add a new entry in the history.
99    pub fn add<S: AsRef<str> + Into<String>>(&mut self, line: S) -> bool {
100        if self.max_len == 0 {
101            return false;
102        }
103        if line.as_ref().is_empty()
104            || (self.ignore_space
105                && line
106                    .as_ref()
107                    .chars()
108                    .next()
109                    .map_or(true, char::is_whitespace))
110        {
111            return false;
112        }
113        if self.ignore_dups {
114            if let Some(s) = self.entries.back() {
115                if s == line.as_ref() {
116                    return false;
117                }
118            }
119        }
120        if self.entries.len() == self.max_len {
121            self.entries.pop_front();
122        }
123        self.entries.push_back(line.into());
124        self.new_entries = self.new_entries.saturating_add(1).min(self.len());
125        true
126    }
127
128    /// Return the number of entries in the history.
129    #[must_use]
130    pub fn len(&self) -> usize {
131        self.entries.len()
132    }
133
134    /// Return true if the history has no entry.
135    #[must_use]
136    pub fn is_empty(&self) -> bool {
137        self.entries.is_empty()
138    }
139
140    /// Set the maximum length for the history. This function can be called even
141    /// if there is already some history, the function will make sure to retain
142    /// just the latest `len` elements if the new history length value is
143    /// smaller than the amount of items already inside the history.
144    ///
145    /// Like [stifle_history](http://tiswww.case.edu/php/chet/readline/history.html#IDX11).
146    pub fn set_max_len(&mut self, len: usize) {
147        self.max_len = len;
148        if self.len() > len {
149            self.entries.drain(..self.len() - len);
150            self.new_entries = self.new_entries.min(len);
151        }
152    }
153
154    /// Save the history in the specified file.
155    // TODO history_truncate_file
156    // https://tiswww.case.edu/php/chet/readline/history.html#IDX31
157    pub fn save<P: AsRef<Path> + ?Sized>(&mut self, path: &P) -> Result<()> {
158        if self.is_empty() || self.new_entries == 0 {
159            return Ok(());
160        }
161        let path = path.as_ref();
162        let old_umask = umask();
163        let f = File::create(path);
164        restore_umask(old_umask);
165        let file = f?;
166        let mut lock = RwLock::new(file);
167        let lock_guard = lock.write()?;
168        self.save_to(&lock_guard, false)?;
169        self.new_entries = 0;
170        self.update_path(path, &lock_guard, self.len())
171    }
172
173    fn save_to(&mut self, file: &File, append: bool) -> Result<()> {
174        use std::io::{BufWriter, Write};
175
176        fix_perm(file);
177        let mut wtr = BufWriter::new(file);
178        let first_new_entry = if append {
179            self.entries.len().saturating_sub(self.new_entries)
180        } else {
181            wtr.write_all(Self::FILE_VERSION_V2.as_bytes())?;
182            wtr.write_all(b"\n")?;
183            0
184        };
185        for entry in self.entries.iter().skip(first_new_entry) {
186            let mut bytes = entry.as_bytes();
187            while let Some(i) = memchr::memchr2(b'\\', b'\n', bytes) {
188                let (head, tail) = bytes.split_at(i);
189                wtr.write_all(head)?;
190
191                let (&escapable_byte, tail) = tail
192                    .split_first()
193                    .expect("memchr guarantees i is a valid index");
194                if escapable_byte == b'\n' {
195                    wtr.write_all(br"\n")?; // escaped line feed
196                } else {
197                    debug_assert_eq!(escapable_byte, b'\\');
198                    wtr.write_all(br"\\")?; // escaped backslash
199                }
200                bytes = tail;
201            }
202            wtr.write_all(bytes)?; // remaining bytes with no \n or \
203            wtr.write_all(b"\n")?;
204        }
205        // https://github.com/rust-lang/rust/issues/32677#issuecomment-204833485
206        wtr.flush()?;
207        Ok(())
208    }
209
210    /// Append new entries in the specified file.
211    // Like [append_history](http://tiswww.case.edu/php/chet/readline/history.html#IDX30).
212    pub fn append<P: AsRef<Path> + ?Sized>(&mut self, path: &P) -> Result<()> {
213        use std::io::Seek;
214
215        if self.is_empty() || self.new_entries == 0 {
216            return Ok(());
217        }
218        let path = path.as_ref();
219        if !path.exists() || self.new_entries == self.max_len {
220            return self.save(path);
221        }
222        let file = OpenOptions::new().write(true).read(true).open(path)?;
223        let mut lock = RwLock::new(file);
224        let mut lock_guard = lock.write()?;
225        if self.can_just_append(path, &lock_guard)? {
226            lock_guard.seek(SeekFrom::End(0))?;
227            self.save_to(&lock_guard, true)?;
228            let size = self
229                .path_info
230                .as_ref()
231                .unwrap()
232                .2
233                .saturating_add(self.new_entries);
234            self.new_entries = 0;
235            return self.update_path(path, &lock_guard, size);
236        }
237        // we may need to truncate file before appending new entries
238        let mut other = Self {
239            entries: VecDeque::new(),
240            max_len: self.max_len,
241            ignore_space: self.ignore_space,
242            ignore_dups: self.ignore_dups,
243            new_entries: 0,
244            path_info: None,
245        };
246        other.load_from(&lock_guard)?;
247        let first_new_entry = self.entries.len().saturating_sub(self.new_entries);
248        for entry in self.entries.iter().skip(first_new_entry) {
249            other.add(entry);
250        }
251        lock_guard.seek(SeekFrom::Start(0))?;
252        lock_guard.set_len(0)?; // if new size < old size
253        other.save_to(&lock_guard, false)?;
254        self.update_path(path, &lock_guard, other.len())?;
255        self.new_entries = 0;
256        Ok(())
257    }
258
259    /// Load the history from the specified file.
260    ///
261    /// # Errors
262    /// Will return `Err` if path does not already exist or could not be read.
263    pub fn load<P: AsRef<Path> + ?Sized>(&mut self, path: &P) -> Result<()> {
264        let path = path.as_ref();
265        let file = File::open(path)?;
266        let lock = RwLock::new(file);
267        let lock_guard = lock.read()?;
268        let len = self.len();
269        if self.load_from(&lock_guard)? {
270            self.update_path(path, &lock_guard, self.len() - len)
271        } else {
272            // discard old version on next save
273            self.path_info = None;
274            Ok(())
275        }
276    }
277
278    fn load_from(&mut self, file: &File) -> Result<bool> {
279        use std::io::{BufRead, BufReader};
280
281        let rdr = BufReader::new(file);
282        let mut lines = rdr.lines();
283        let mut v2 = false;
284        if let Some(first) = lines.next() {
285            let line = first?;
286            if line == Self::FILE_VERSION_V2 {
287                v2 = true;
288            } else {
289                self.add(line);
290            }
291        }
292        let mut appendable = v2;
293        for line in lines {
294            let mut line = line?;
295            if line.is_empty() {
296                continue;
297            }
298            if v2 {
299                let mut copy = None; // lazily copy line if unescaping is needed
300                let mut str = line.as_str();
301                while let Some(i) = str.find('\\') {
302                    if copy.is_none() {
303                        copy = Some(String::with_capacity(line.len()));
304                    }
305                    let s = copy.as_mut().unwrap();
306                    s.push_str(&str[..i]);
307                    let j = i + 1; // escaped char idx
308                    let b = if j < str.len() {
309                        str.as_bytes()[j]
310                    } else {
311                        0 // unexpected if History::save works properly
312                    };
313                    match b {
314                        b'n' => {
315                            s.push('\n'); // unescaped line feed
316                        }
317                        b'\\' => {
318                            s.push('\\'); // unescaped back slash
319                        }
320                        _ => {
321                            // only line feed and back slash should have been escaped
322                            warn!(target: "rustyline", "bad escaped line: {}", line);
323                            copy = None;
324                            break;
325                        }
326                    }
327                    str = &str[j + 1..];
328                }
329                if let Some(mut s) = copy {
330                    s.push_str(str); // remaining bytes with no escaped char
331                    line = s;
332                }
333            }
334            appendable &= self.add(line); // TODO truncate to MAX_LINE
335        }
336        self.new_entries = 0; // TODO we may lost new entries if loaded lines < max_len
337        Ok(appendable)
338    }
339
340    fn update_path(&mut self, path: &Path, file: &File, size: usize) -> Result<()> {
341        let modified = file.metadata()?.modified()?;
342        if let Some(PathInfo(
343            ref mut previous_path,
344            ref mut previous_modified,
345            ref mut previous_size,
346        )) = self.path_info
347        {
348            if previous_path.as_path() != path {
349                *previous_path = path.to_owned();
350            }
351            *previous_modified = modified;
352            *previous_size = size;
353        } else {
354            self.path_info = Some(PathInfo(path.to_owned(), modified, size));
355        }
356        debug!(target: "rustyline", "PathInfo({:?}, {:?}, {})", path, modified, size);
357        Ok(())
358    }
359
360    fn can_just_append(&self, path: &Path, file: &File) -> Result<bool> {
361        if let Some(PathInfo(ref previous_path, ref previous_modified, ref previous_size)) =
362            self.path_info
363        {
364            if previous_path.as_path() != path {
365                debug!(target: "rustyline", "cannot append: {:?} <> {:?}", previous_path, path);
366                return Ok(false);
367            }
368            let modified = file.metadata()?.modified()?;
369            if *previous_modified != modified
370                || self.max_len <= *previous_size
371                || self.max_len < (*previous_size).saturating_add(self.new_entries)
372            {
373                debug!(target: "rustyline", "cannot append: {:?} < {:?} or {} < {} + {}",
374                       previous_modified, modified, self.max_len, previous_size, self.new_entries);
375                Ok(false)
376            } else {
377                Ok(true)
378            }
379        } else {
380            Ok(false)
381        }
382    }
383
384    /// Clear history
385    pub fn clear(&mut self) {
386        self.entries.clear();
387        self.new_entries = 0;
388    }
389
390    /// Search history (start position inclusive [0, len-1]).
391    ///
392    /// Return the absolute index of the nearest history entry that matches
393    /// `term`.
394    ///
395    /// Return None if no entry contains `term` between [start, len -1] for
396    /// forward search
397    /// or between [0, start] for reverse search.
398    #[must_use]
399    pub fn search(&self, term: &str, start: usize, dir: SearchDirection) -> Option<SearchResult> {
400        #[cfg(not(feature = "case_insensitive_history_search"))]
401        {
402            let test = |entry: &str| entry.find(term);
403            self.search_match(term, start, dir, test)
404        }
405        #[cfg(feature = "case_insensitive_history_search")]
406        {
407            use regex::{escape, RegexBuilder};
408            if let Ok(re) = RegexBuilder::new(&escape(term))
409                .case_insensitive(true)
410                .build()
411            {
412                let test = |entry: &str| re.find(entry).map(|m| m.start());
413                self.search_match(term, start, dir, test)
414            } else {
415                None
416            }
417        }
418    }
419
420    /// Anchored search
421    #[must_use]
422    pub fn starts_with(
423        &self,
424        term: &str,
425        start: usize,
426        dir: SearchDirection,
427    ) -> Option<SearchResult> {
428        #[cfg(not(feature = "case_insensitive_history_search"))]
429        {
430            let test = |entry: &str| {
431                if entry.starts_with(term) {
432                    Some(term.len())
433                } else {
434                    None
435                }
436            };
437            self.search_match(term, start, dir, test)
438        }
439        #[cfg(feature = "case_insensitive_history_search")]
440        {
441            use regex::{escape, RegexBuilder};
442            if let Ok(re) = RegexBuilder::new(&escape(term))
443                .case_insensitive(true)
444                .build()
445            {
446                let test = |entry: &str| {
447                    re.find(entry)
448                        .and_then(|m| if m.start() == 0 { Some(m) } else { None })
449                        .map(|m| m.end())
450                };
451                self.search_match(term, start, dir, test)
452            } else {
453                None
454            }
455        }
456    }
457
458    fn search_match<F>(
459        &self,
460        term: &str,
461        start: usize,
462        dir: SearchDirection,
463        test: F,
464    ) -> Option<SearchResult>
465    where
466        F: Fn(&str) -> Option<usize>,
467    {
468        if term.is_empty() || start >= self.len() {
469            return None;
470        }
471        match dir {
472            SearchDirection::Reverse => {
473                for (idx, entry) in self
474                    .entries
475                    .iter()
476                    .rev()
477                    .skip(self.entries.len() - 1 - start)
478                    .enumerate()
479                {
480                    if let Some(cursor) = test(entry) {
481                        return Some(SearchResult {
482                            idx: start - idx,
483                            entry,
484                            pos: cursor,
485                        });
486                    }
487                }
488                None
489            }
490            SearchDirection::Forward => {
491                for (idx, entry) in self.entries.iter().skip(start).enumerate() {
492                    if let Some(cursor) = test(entry) {
493                        return Some(SearchResult {
494                            idx: idx + start,
495                            entry,
496                            pos: cursor,
497                        });
498                    }
499                }
500                None
501            }
502        }
503    }
504
505    /// Return a forward iterator.
506    #[must_use]
507    pub fn iter(&self) -> Iter<'_> {
508        Iter(self.entries.iter())
509    }
510}
511
512impl Index<usize> for History {
513    type Output = String;
514
515    fn index(&self, index: usize) -> &String {
516        &self.entries[index]
517    }
518}
519
520impl<'a> IntoIterator for &'a History {
521    type IntoIter = Iter<'a>;
522    type Item = &'a String;
523
524    fn into_iter(self) -> Iter<'a> {
525        self.iter()
526    }
527}
528
529/// History iterator.
530pub struct Iter<'a>(vec_deque::Iter<'a, String>);
531
532impl<'a> Iterator for Iter<'a> {
533    type Item = &'a String;
534
535    fn next(&mut self) -> Option<&'a String> {
536        self.0.next()
537    }
538
539    fn size_hint(&self) -> (usize, Option<usize>) {
540        self.0.size_hint()
541    }
542}
543
544impl<'a> DoubleEndedIterator for Iter<'a> {
545    fn next_back(&mut self) -> Option<&'a String> {
546        self.0.next_back()
547    }
548}
549
550cfg_if::cfg_if! {
551    if #[cfg(any(windows, target_arch = "wasm32"))] {
552        fn umask() -> u16 {
553            0
554        }
555
556        fn restore_umask(_: u16) {}
557
558        fn fix_perm(_: &File) {}
559    } else if #[cfg(unix)] {
560        use nix::sys::stat::{self, Mode, fchmod};
561        fn umask() -> Mode {
562            stat::umask(Mode::S_IXUSR | Mode::S_IRWXG | Mode::S_IRWXO)
563        }
564
565        fn restore_umask(old_umask: Mode) {
566            stat::umask(old_umask);
567        }
568
569        fn fix_perm(file: &File) {
570            use std::os::unix::io::AsRawFd;
571            let _ = fchmod(file.as_raw_fd(), Mode::S_IRUSR | Mode::S_IWUSR);
572        }
573    }
574}
575
576#[cfg(test)]
577mod tests {
578    use super::{History, SearchDirection, SearchResult};
579    use crate::config::Config;
580    use crate::Result;
581
582    fn init() -> History {
583        let mut history = History::new();
584        assert!(history.add("line1"));
585        assert!(history.add("line2"));
586        assert!(history.add("line3"));
587        history
588    }
589
590    #[test]
591    fn new() {
592        let history = History::new();
593        assert_eq!(0, history.entries.len());
594    }
595
596    #[test]
597    fn add() {
598        let config = Config::builder().history_ignore_space(true).build();
599        let mut history = History::with_config(config);
600        assert_eq!(config.max_history_size(), history.max_len);
601        assert!(history.add("line1"));
602        assert!(history.add("line2"));
603        assert!(!history.add("line2"));
604        assert!(!history.add(""));
605        assert!(!history.add(" line3"));
606    }
607
608    #[test]
609    fn set_max_len() {
610        let mut history = init();
611        history.set_max_len(1);
612        assert_eq!(1, history.entries.len());
613        assert_eq!(Some(&"line3".to_owned()), history.last());
614    }
615
616    #[test]
617    #[cfg_attr(miri, ignore)] // unsupported operation: `getcwd` not available when isolation is enabled
618    fn save() -> Result<()> {
619        check_save("line\nfour \\ abc")
620    }
621
622    #[test]
623    #[cfg_attr(miri, ignore)] // unsupported operation: `open` not available when isolation is enabled
624    fn save_windows_path() -> Result<()> {
625        let path = "cd source\\repos\\forks\\nushell\\";
626        check_save(path)
627    }
628
629    fn check_save(line: &str) -> Result<()> {
630        let mut history = init();
631        assert!(history.add(line));
632        let tf = tempfile::NamedTempFile::new()?;
633
634        history.save(tf.path())?;
635        let mut history2 = History::new();
636        history2.load(tf.path())?;
637        for (a, b) in history.entries.iter().zip(history2.entries.iter()) {
638            assert_eq!(a, b);
639        }
640        tf.close()?;
641        Ok(())
642    }
643
644    #[test]
645    #[cfg_attr(miri, ignore)] // unsupported operation: `getcwd` not available when isolation is enabled
646    fn load_legacy() -> Result<()> {
647        use std::io::Write;
648        let tf = tempfile::NamedTempFile::new()?;
649        {
650            let mut legacy = std::fs::File::create(tf.path())?;
651            // Some data we'd accidentally corrupt if we got the version wrong
652            let data = b"\
653                test\\n \\abc \\123\n\
654                123\\n\\\\n\n\
655                abcde
656            ";
657            legacy.write_all(data)?;
658            legacy.flush()?;
659        }
660        let mut history = History::new();
661        history.load(tf.path())?;
662        assert_eq!(history.entries[0], "test\\n \\abc \\123");
663        assert_eq!(history.entries[1], "123\\n\\\\n");
664        assert_eq!(history.entries[2], "abcde");
665
666        tf.close()?;
667        Ok(())
668    }
669
670    #[test]
671    #[cfg_attr(miri, ignore)] // unsupported operation: `getcwd` not available when isolation is enabled
672    fn append() -> Result<()> {
673        let mut history = init();
674        let tf = tempfile::NamedTempFile::new()?;
675
676        history.append(tf.path())?;
677
678        let mut history2 = History::new();
679        history2.load(tf.path())?;
680        history2.add("line4");
681        history2.append(tf.path())?;
682
683        history.add("line5");
684        history.append(tf.path())?;
685
686        let mut history3 = History::new();
687        history3.load(tf.path())?;
688        assert_eq!(history3.len(), 5);
689
690        tf.close()?;
691        Ok(())
692    }
693
694    #[test]
695    #[cfg_attr(miri, ignore)] // unsupported operation: `getcwd` not available when isolation is enabled
696    fn truncate() -> Result<()> {
697        let tf = tempfile::NamedTempFile::new()?;
698
699        let config = Config::builder().history_ignore_dups(false).build();
700        let mut history = History::with_config(config);
701        history.add("line1");
702        history.add("line1");
703        history.append(tf.path())?;
704
705        let mut history = History::new();
706        history.load(tf.path())?;
707        history.add("l");
708        history.append(tf.path())?;
709
710        let mut history = History::new();
711        history.load(tf.path())?;
712        assert_eq!(history.len(), 2);
713        assert_eq!(history.entries[1], "l");
714
715        tf.close()?;
716        Ok(())
717    }
718
719    #[test]
720    fn search() {
721        let history = init();
722        assert_eq!(None, history.search("", 0, SearchDirection::Forward));
723        assert_eq!(None, history.search("none", 0, SearchDirection::Forward));
724        assert_eq!(None, history.search("line", 3, SearchDirection::Forward));
725
726        assert_eq!(
727            Some(SearchResult {
728                idx: 0,
729                entry: history.get(0).unwrap(),
730                pos: 0
731            }),
732            history.search("line", 0, SearchDirection::Forward)
733        );
734        assert_eq!(
735            Some(SearchResult {
736                idx: 1,
737                entry: history.get(1).unwrap(),
738                pos: 0
739            }),
740            history.search("line", 1, SearchDirection::Forward)
741        );
742        assert_eq!(
743            Some(SearchResult {
744                idx: 2,
745                entry: history.get(2).unwrap(),
746                pos: 0
747            }),
748            history.search("line3", 1, SearchDirection::Forward)
749        );
750    }
751
752    #[test]
753    fn reverse_search() {
754        let history = init();
755        assert_eq!(None, history.search("", 2, SearchDirection::Reverse));
756        assert_eq!(None, history.search("none", 2, SearchDirection::Reverse));
757        assert_eq!(None, history.search("line", 3, SearchDirection::Reverse));
758
759        assert_eq!(
760            Some(SearchResult {
761                idx: 2,
762                entry: history.get(2).unwrap(),
763                pos: 0
764            }),
765            history.search("line", 2, SearchDirection::Reverse)
766        );
767        assert_eq!(
768            Some(SearchResult {
769                idx: 1,
770                entry: history.get(1).unwrap(),
771                pos: 0
772            }),
773            history.search("line", 1, SearchDirection::Reverse)
774        );
775        assert_eq!(
776            Some(SearchResult {
777                idx: 0,
778                entry: history.get(0).unwrap(),
779                pos: 0
780            }),
781            history.search("line1", 1, SearchDirection::Reverse)
782        );
783    }
784
785    #[test]
786    #[cfg(feature = "case_insensitive_history_search")]
787    fn anchored_search() {
788        let history = init();
789        assert_eq!(
790            Some(SearchResult {
791                idx: 2,
792                entry: history.get(2).unwrap(),
793                pos: 4
794            }),
795            history.starts_with("LiNe", 2, SearchDirection::Reverse)
796        );
797        assert_eq!(
798            None,
799            history.starts_with("iNe", 2, SearchDirection::Reverse)
800        );
801    }
802}
rustyline/history.rs

rustyline/
history.rs
