How is CTRL-R (reverse-i-search) is implemented in bash terminal?

Question

Example of the reverse search:

(reverse-i-search)`grep': git log | grep master

What is the algorithm used to find a suggestion? Where does its search space come from ?

A pointer to its source code would be greatly appreciated.

Answer 1

Reverse-i-search is part of GNU Readline Library. The Readline Library facilitates reading line along with editing facilities. The entire source code can be found here.

Source of search space

Following code snippet from the source shows how the source file for history is determined :

/* Return the string that should be used in the place of this
   filename.  This only matters when you dont specify the
   filename to read_history (), or write_history (). */
static char *
history_filename (filename)
     const char *filename;
{
  char *return_val;
  const char *home;
  int home_len;

  return_val = filename ? savestring (filename) : (char *)NULL;

  if (return_val)
    return (return_val);

  home = sh_get_env_value ("HOME");
#if defined (_WIN32)
  if (home == 0)
    home = sh_get_env_value ("APPDATA");
#endif

  if (home == 0)
    return (NULL);
  else
    home_len = strlen (home);

  return_val = (char *)xmalloc (2 + home_len + 8); /* strlen(".history") == 8 */
  strcpy (return_val, home);
  return_val[home_len] = '/';
#if defined (__MSDOS__)
  strcpy (return_val + home_len + 1, "_history");
#else
  strcpy (return_val + home_len + 1, ".history");
#endif

  return (return_val);
}

• savestring() is defined in savestring.c which simply copies the string filename if it is defined.
• sh_get_env_value() function is implemented using getenv() function ( provided by <stdlib.h> ) used to get an environment value ( Refer man page getenv(3) ).
• As shown, .bash_history or .history ( this is the file that is used in case the function returns NULL ) will be used as source for implementing the search on a Linux system.

Source : histfile.c

How history is stored

• The searchable history is stored in a HIST_ENTRY( history list ) array. The data from .bash_history is added to this array. Source : history.c
• The record of the commands entered in current session are saved in _rl_saved_line_for_history.
• These two are combined into a _rl_search_cxt instance member array ( cxt->lines[] ) using which the search is performed.

Algorithm

The actual search is performed using _rl_isearch_dispatch() and _rl_search_getchar() function.

Short Summary : The algorithm reads character by character the input deciding what it should do. In case of no interrupts, it adds the character to the search string searching for it in the array. If the string is not found, it moves to next element skipping over same string found again and strings shorter in length than current length of search string. ( Read default : in switch for exact details in _rl_isearch_dispatch() )

In case the string is not found, the bell is dinged. Else, it displays the string but doesn't actually moves there in history list till user accepts the location.