readline,repl: add substring based history search

This improves the current history search feature by adding substring based history search similar to ZSH. In case the `UP` or `DOWN` buttons are pressed after writing a few characters, the start string up to the current cursor is used to search the history. All other history features work exactly as they used to. Fixes: #28437
BridgeAR · Dec 26, 2019 · Dec 27, 2019 · Dec 27, 2019 · Dec 29, 2019 · Dec 31, 2019
commit 470e87fbd8e638e1418e30d565167bb70af12d40
diff --git a/doc/api/repl.md b/doc/api/repl.md
@@ -22,10 +22,11 @@ be connected to any Node.js [stream][].
 
 Instances of [`repl.REPLServer`][] support automatic completion of inputs,
 completion preview, simplistic Emacs-style line editing, multi-line inputs,
-[ZSH][] like reverse-i-search, ANSI-styled output, saving and restoring current
-REPL session state, error recovery, and customizable evaluation functions.
-Terminals that do not support ANSI-styles and Emacs-style line editing
-automatically fall back to a limited feature set.
+[ZSH][]-like reverse-i-search, [ZSH][]-like substring-based history search,
+ANSI-styled output, saving and restoring current REPL session state, error
+recovery, and customizable evaluation functions. Terminals that do not support
+ANSI styles and Emacs-style line editing automatically fall back to a limited
+feature set.
 
 ### Commands and Special Keys
 

diff --git a/lib/internal/readline/utils.js b/lib/internal/readline/utils.js
@@ -4,6 +4,7 @@ const {
   Boolean,
   NumberIsInteger,
   RegExp,
+  Symbol,
 } = primordials;
 
 // Regex used for ansi escape code splitting
@@ -17,6 +18,7 @@ const ansi = new RegExp(ansiPattern, 'g');
 
 const kUTF16SurrogateThreshold = 0x10000; // 2 ** 16
 const kEscape = '\x1b';
+const kSubstringSearch = Symbol('kSubstringSearch');
 
 let getStringWidth;
 let isFullWidthCodePoint;
@@ -470,6 +472,7 @@ module.exports = {
   emitKeys,
   getStringWidth,
   isFullWidthCodePoint,
+  kSubstringSearch,
   kUTF16SurrogateThreshold,
   stripVTControlCharacters,
   CSI

diff --git a/lib/internal/repl/utils.js b/lib/internal/repl/utils.js
@@ -33,6 +33,7 @@ const {
 const {
   commonPrefix,
   getStringWidth,
+  kSubstringSearch,
 } = require('internal/readline/utils');
 
 const { inspect } = require('util');
@@ -646,6 +647,7 @@ function setupReverseSearch(repl) {
                typeof string !== 'string' ||
                string === '') {
       reset();
+      repl[kSubstringSearch] = '';
     } else {
       reset(`${input}${string}`);
       search();

diff --git a/lib/readline.js b/lib/readline.js
@@ -54,6 +54,7 @@ const {
   emitKeys,
   getStringWidth,
   isFullWidthCodePoint,
+  kSubstringSearch,
   kUTF16SurrogateThreshold,
   stripVTControlCharacters
 } = require('internal/readline/utils');
@@ -153,6 +154,7 @@ function Interface(input, output, completer, terminal) {
 
   const self = this;
 
+  this[kSubstringSearch] = null;
   this.output = output;
   this.input = input;
   this.historySize = historySize;
@@ -688,34 +690,51 @@ Interface.prototype._line = function() {
   this._onLine(line);
 };
 
-
+// TODO(BridgeAR): Add underscores to the search part and a red background in
+// case no match is found. This should only be the visual part and not the
+// actual line content!
+// TODO(BridgeAR): In case the substring based search is active and the end is
+// reached, show a comment how to search the history as before. E.g., using
+// <ctrl> + N. Only show this after two/three UPs or DOWNs, not on the first
+// one.
 Interface.prototype._historyNext = function() {
-  if (this.historyIndex > 0) {
-    this.historyIndex--;
-    this.line = this.history[this.historyIndex];
+  if (this.historyIndex >= 0) {
+    const search = this[kSubstringSearch] || '';
+    let index = this.historyIndex - 1;
+    while (index >= 0 &&
+           !this.history[index].startsWith(search)) {
+      index--;
+    }
+    if (index === -1) {
+      this.line = search;
+    } else {
+      this.line = this.history[index];
+    }
+    this.historyIndex = index;
     this.cursor = this.line.length; // Set cursor to end of line.
     this._refreshLine();
-
-  } else if (this.historyIndex === 0) {
-    this.historyIndex = -1;
-    this.cursor = 0;
-    this.line = '';
-    this._refreshLine();
   }
 };
 
-
 Interface.prototype._historyPrev = function() {
-  if (this.historyIndex + 1 < this.history.length) {
-    this.historyIndex++;
-    this.line = this.history[this.historyIndex];
+  if (this.historyIndex < this.history.length) {
+    const search = this[kSubstringSearch] || '';
+    let index = this.historyIndex + 1;
+    while (index < this.history.length &&
+           !this.history[index].startsWith(search)) {
+      index++;
+    }
+    if (index === this.history.length) {
+      return;
+    } else {
+      this.line = this.history[index];
+    }
+    this.historyIndex = index;
     this.cursor = this.line.length; // Set cursor to end of line.
-
     this._refreshLine();
   }
 };
 
-
 // Returns the last character's display position of the given string
 Interface.prototype._getDisplayPos = function(str) {
   let offset = 0;
@@ -856,6 +875,20 @@ Interface.prototype._ttyWrite = function(s, key) {
   key = key || {};
   this._previousKey = key;
 
+  // Activate or deactivate substring search.
+  if ((key.name === 'up' || key.name === 'down') &&
+      !key.ctrl && !key.meta && !key.shift) {
+    if (this[kSubstringSearch] === null) {
+      this[kSubstringSearch] = this.line.slice(0, this.cursor);
+    }
+  } else if (this[kSubstringSearch] !== null) {
+    this[kSubstringSearch] = null;
+    // Reset the index in case there's no match.
+    if (this.history.length === this.historyIndex) {
+      this.historyIndex = -1;
+    }
+  }
+
   // Ignore escape key, fixes
   // https://github.com/nodejs/node-v0.x-archive/issues/2876.
   if (key.name === 'escape') return;

diff --git a/test/parallel/test-readline-interface.js b/test/parallel/test-readline-interface.js
@@ -430,6 +430,7 @@ function isWarned(emitter) {
       removeHistoryDuplicates: true
     });
     const expectedLines = ['foo', 'bar', 'baz', 'bar', 'bat', 'bat'];
+    // ['foo', 'baz', 'bar', bat'];
     let callCount = 0;
     rli.on('line', function(line) {
       assert.strictEqual(line, expectedLines[callCount]);
@@ -450,12 +451,43 @@ function isWarned(emitter) {
     assert.strictEqual(callCount, 0);
     fi.emit('keypress', '.', { name: 'down' }); // 'baz'
     assert.strictEqual(rli.line, 'baz');
+    assert.strictEqual(rli.historyIndex, 2);
     fi.emit('keypress', '.', { name: 'n', ctrl: true }); // 'bar'
     assert.strictEqual(rli.line, 'bar');
+    assert.strictEqual(rli.historyIndex, 1);
+    fi.emit('keypress', '.', { name: 'n', ctrl: true });
+    assert.strictEqual(rli.line, 'bat');
+    assert.strictEqual(rli.historyIndex, 0);
+    // Activate the substring history search.
     fi.emit('keypress', '.', { name: 'down' }); // 'bat'
     assert.strictEqual(rli.line, 'bat');
-    fi.emit('keypress', '.', { name: 'down' }); // ''
-    assert.strictEqual(rli.line, '');
+    assert.strictEqual(rli.historyIndex, -1);
+    // Deactivate substring history search.
+    fi.emit('keypress', '.', { name: 'backspace' }); // 'ba'
+    assert.strictEqual(rli.historyIndex, -1);
+    assert.strictEqual(rli.line, 'ba');
+    // Activate the substring history search.
+    fi.emit('keypress', '.', { name: 'down' }); // 'ba'
+    assert.strictEqual(rli.historyIndex, -1);
+    assert.strictEqual(rli.line, 'ba');
+    fi.emit('keypress', '.', { name: 'down' }); // 'ba'
+    assert.strictEqual(rli.historyIndex, -1);
+    assert.strictEqual(rli.line, 'ba');
+    fi.emit('keypress', '.', { name: 'up' }); // 'bat'
+    assert.strictEqual(rli.historyIndex, 0);
+    assert.strictEqual(rli.line, 'bat');
+    fi.emit('keypress', '.', { name: 'up' }); // 'bar'
+    assert.strictEqual(rli.historyIndex, 1);
+    assert.strictEqual(rli.line, 'bar');
+    fi.emit('keypress', '.', { name: 'up' }); // 'baz'
+    assert.strictEqual(rli.historyIndex, 2);
+    assert.strictEqual(rli.line, 'baz');
+    fi.emit('keypress', '.', { name: 'up' }); // 'baz'
+    assert.strictEqual(rli.historyIndex, 2);
+    assert.strictEqual(rli.line, 'baz');
+    fi.emit('keypress', '.', { name: 'up' }); // 'baz'
+    assert.strictEqual(rli.historyIndex, 2);
+    assert.strictEqual(rli.line, 'baz');
     rli.close();
   }
 

diff --git a/test/parallel/test-repl-history-navigation.js b/test/parallel/test-repl-history-navigation.js
@@ -78,6 +78,7 @@ const tests = [
   },
   {
     env: { NODE_REPL_HISTORY: defaultHistoryPath },
+    checkTotal: true,
     test: [UP, UP, UP, UP, UP, DOWN, DOWN, DOWN, DOWN],
     expected: [prompt,
                `${prompt}Array(100).fill(1).map((e, i) => i ** 2)`,
@@ -102,6 +103,52 @@ const tests = [
                  '1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936,' +
                  ' 2025, 2116, 2209,...',
                prompt].filter((e) => typeof e === 'string'),
+    clean: false
+  },
+  { // Creates more history entries to navigate through.
+    env: { NODE_REPL_HISTORY: defaultHistoryPath },
+    test: [
+      '555 + 909', ENTER, // Add a duplicate to the history set.
+      'const foo = true', ENTER,
+      '555n + 111n', ENTER,
+      '5 + 5', ENTER,
+      '55 - 13 === 42', ENTER
+    ],
+    expected: [],
+    clean: false
+  },
+  {
+    env: { NODE_REPL_HISTORY: defaultHistoryPath },
+    checkTotal: true,
+    preview: false,
+    showEscapeCodes: true,
+    test: [
+      '55', UP, UP, UP, UP, UP, UP, ENTER
+    ],
+    expected: [
+      '\x1B[1G', '\x1B[0J', prompt, '\x1B[3G',
+      // '55'
+      '5', '5',
+      // UP
+      '\x1B[1G', '\x1B[0J',
+      '> 55 - 13 === 42', '\x1B[17G',
+      // UP - skipping 5 + 5
+      '\x1B[1G', '\x1B[0J',
+      '> 555n + 111n', '\x1B[14G',
+      // UP - skipping const foo = true
+      '\x1B[1G', '\x1B[0J',
+      '> 555 + 909', '\x1B[12G',
+      // UP - matching the identical history entry again.
+      '\x1B[1G', '\x1B[0J',
+      '> 555 + 909',
+      // UP, UP, ENTER. UPs at the end of the history have no effect.
+      '\x1B[12G',
+      '\r\n',
+      '1464\n',
+      '\x1B[1G', '\x1B[0J',
+      '> ', '\x1B[3G',
+      '\r\n'
+    ],
     clean: true
   },
   {
@@ -190,7 +237,7 @@ const tests = [
       '\x1B[1B', '\x1B[2K', '\x1B[1A',
       // 6. Backspace
       '\x1B[1G', '\x1B[0J',
-      prompt, '\x1B[3G'
+      prompt, '\x1B[3G', '\r\n'
     ],
     clean: true
   },
@@ -259,6 +306,11 @@ const tests = [
       // 10. Word right. Cleanup
       '\x1B[0K', '\x1B[3G', '\x1B[7C', ' // n', '\x1B[10G',
       '\x1B[0K',
+      // 11. ENTER
+      '\r\n',
+      'Uncaught ReferenceError: functio is not defined\n',
+      '\x1B[1G', '\x1B[0J',
+      prompt, '\x1B[3G', '\r\n'
     ],
     clean: true
   },
@@ -300,6 +352,7 @@ const tests = [
       prompt,
       's',
       ' // Always visible',
+      prompt,
     ],
     clean: true
   }
@@ -330,8 +383,8 @@ function runTest() {
     setImmediate(runTestWrap, true);
     return;
   }
-
   const lastChunks = [];
+  let i = 0;
 
   REPL.createInternalRepl(opts.env, {
     input: new ActionStream(),
@@ -344,19 +397,20 @@ function runTest() {
           return next();
         }
 
-        lastChunks.push(inspect(output));
+        lastChunks.push(output);
 
-        if (expected.length) {
+        if (expected.length && !opts.checkTotal) {
           try {
-            assert.strictEqual(output, expected[0]);
+            assert.strictEqual(output, expected[i]);
           } catch (e) {
             console.error(`Failed test # ${numtests - tests.length}`);
             console.error('Last outputs: ' + inspect(lastChunks, {
               breakLength: 5, colors: true
             }));
             throw e;
           }
-          expected.shift();
+          // TODO(BridgeAR): Auto close on last chunk!
+          i++;
         }
 
         next();
@@ -365,6 +419,7 @@ function runTest() {
     completer: opts.completer,
     prompt,
     useColors: false,
+    preview: opts.preview,
     terminal: true
   }, function(err, repl) {
     if (err) {
@@ -376,9 +431,13 @@ function runTest() {
       if (opts.clean)
         cleanupTmpFile();
 
-      if (expected.length !== 0) {
+      if (opts.checkTotal) {
+        assert.deepStrictEqual(lastChunks, expected);
+      } else if (expected.length !== i) {
+        console.error(tests[numtests - tests.length - 1]);
         throw new Error(`Failed test # ${numtests - tests.length}`);
       }
+
       setImmediate(runTestWrap, true);
     });
 

diff --git a/test/parallel/test-repl-reverse-search.js b/test/parallel/test-repl-reverse-search.js
@@ -309,10 +309,9 @@ function runTest() {
 
         lastChunks.push(output);
 
-        if (expected.length) {
+        if (expected.length && !opts.checkTotal) {
           try {
-            if (!opts.checkTotal)
-              assert.strictEqual(output, expected[i]);
+            assert.strictEqual(output, expected[i]);
           } catch (e) {
             console.error(`Failed test # ${numtests - tests.length}`);
             console.error('Last outputs: ' + inspect(lastChunks, {
@@ -342,7 +341,8 @@ function runTest() {
 
       if (opts.checkTotal) {
         assert.deepStrictEqual(lastChunks, expected);
-      } else if (expected.length !== 0) {
+      } else if (expected.length !== i) {
+        console.error(tests[numtests - tests.length - 1]);
         throw new Error(`Failed test # ${numtests - tests.length}`);
       }