readline/isearch.c

   1 /* **************************************************************** */
   2 /*                                                                  */
   3 /*                      I-Search and Searching                      */
   4 /*                                                                  */
   5 /* **************************************************************** */
   6
   7 /* Copyright (C) 1987-2002 Free Software Foundation, Inc.
   8
   9    This file contains the Readline Library (the Library), a set of
  10    routines for providing Emacs style line input to programs that ask
  11    for it.
  12
  13    The Library is free software; you can redistribute it and/or modify
  14    it under the terms of the GNU General Public License as published by
  15    the Free Software Foundation; either version 2, or (at your option)
  16    any later version.
  17
  18    The Library is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    The GNU General Public License is often shipped with GNU software, and
  24    is generally kept in a file called COPYING or LICENSE.  If you do not
  25    have a copy of the license, write to the Free Software Foundation,
  26    59 Temple Place, Suite 330, Boston, MA 02111 USA. */
  27 #define READLINE_LIBRARY
  28
  29 #if defined (HAVE_CONFIG_H)
  30 #  include <config.h>
  31 #endif
  32
  33 #include <sys/types.h>
  34
  35 #include <stdio.h>
  36
  37 #if defined (HAVE_UNISTD_H)
  38 #  include <unistd.h>
  39 #endif
  40
  41 #if defined (HAVE_STDLIB_H)
  42 #  include <stdlib.h>
  43 #else
  44 #  include "ansi_stdlib.h"
  45 #endif
  46
  47 #include "rldefs.h"
  48 #include "rlmbutil.h"
  49
  50 #include "readline.h"
  51 #include "history.h"
  52
  53 #include "rlprivate.h"
  54 #include "xmalloc.h"
  55
  56 /* Variables exported to other files in the readline library. */
  57 char *_rl_isearch_terminators = (char *)NULL;
  58
  59 /* Variables imported from other files in the readline library. */
  60 extern HIST_ENTRY *_rl_saved_line_for_history;
  61
  62 /* Forward declarations */
  63 static int rl_search_history PARAMS((int, int));
  64
  65 /* Last line found by the current incremental search, so we don't `find'
  66    identical lines many times in a row. */
  67 static char *prev_line_found;
  68
  69 /* Last search string and its length. */
  70 static char *last_isearch_string;
  71 static int last_isearch_string_len;
  72
  73 static char *default_isearch_terminators = "\033\012";
  74
  75 /* Search backwards through the history looking for a string which is typed
  76    interactively.  Start with the current line. */
  77 int
  78 rl_reverse_search_history (sign, key)
  79      int sign, key;
  80 {
  81   return (rl_search_history (-sign, key));
  82 }
  83
  84 /* Search forwards through the history looking for a string which is typed
  85    interactively.  Start with the current line. */
  86 int
  87 rl_forward_search_history (sign, key)
  88      int sign, key;
  89 {
  90   return (rl_search_history (sign, key));
  91 }
  92
  93 /* Display the current state of the search in the echo-area.
  94    SEARCH_STRING contains the string that is being searched for,
  95    DIRECTION is zero for forward, or 1 for reverse,
  96    WHERE is the history list number of the current line.  If it is
  97    -1, then this line is the starting one. */
  98 static void
  99 rl_display_search (search_string, reverse_p, where)
 100      char *search_string;
 101      int reverse_p, where;
 102 {
 103   char *message;
 104   int msglen, searchlen;
 105
 106   searchlen = (search_string && *search_string) ? strlen (search_string) : 0;
 107
 108   message = (char *)xmalloc (searchlen + 33);
 109   msglen = 0;
 110
 111 #if defined (NOTDEF)
 112   if (where != -1)
 113     {
 114       sprintf (message, "[%d]", where + history_base);
 115       msglen = strlen (message);
 116     }
 117 #endif /* NOTDEF */
 118
 119   message[msglen++] = '(';
 120
 121   if (reverse_p)
 122     {
 123       strcpy (message + msglen, "reverse-");
 124       msglen += 8;
 125     }
 126
 127   strcpy (message + msglen, "i-search)`");
 128   msglen += 10;
 129
 130   if (search_string)
 131     {
 132       strcpy (message + msglen, search_string);
 133       msglen += searchlen;
 134     }
 135
 136   strcpy (message + msglen, "': ");
 137
 138   rl_message ("%s", message);
 139   free (message);
 140   (*rl_redisplay_function) ();
 141 }
 142
 143 /* Search through the history looking for an interactively typed string.
 144    This is analogous to i-search.  We start the search in the current line.
 145    DIRECTION is which direction to search; >= 0 means forward, < 0 means
 146    backwards. */
 147 static int
 148 rl_search_history (direction, invoking_key)
 149      int direction, invoking_key;
 150 {
 151   /* The string that the user types in to search for. */
 152   char *search_string;
 153
 154   /* The current length of SEARCH_STRING. */
 155   int search_string_index;
 156
 157   /* The amount of space that SEARCH_STRING has allocated to it. */
 158   int search_string_size;
 159
 160   /* The list of lines to search through. */
 161   char **lines, *allocated_line;
 162
 163   /* The length of LINES. */
 164   int hlen;
 165
 166   /* Where we get LINES from. */
 167   HIST_ENTRY **hlist;
 168
 169   register int i;
 170   int orig_point, orig_mark, orig_line, last_found_line;
 171   int c, found, failed, sline_len;
 172   int n, wstart, wlen;
 173 #if defined (HANDLE_MULTIBYTE)
 174   char mb[MB_LEN_MAX];
 175 #endif
 176
 177   /* The line currently being searched. */
 178   char *sline;
 179
 180   /* Offset in that line. */
 181   int line_index;
 182
 183   /* Non-zero if we are doing a reverse search. */
 184   int reverse;
 185
 186   /* The list of characters which terminate the search, but are not
 187      subsequently executed.  If the variable isearch-terminators has
 188      been set, we use that value, otherwise we use ESC and C-J. */
 189   char *isearch_terminators;
 190
 191   RL_SETSTATE(RL_STATE_ISEARCH);
 192   orig_point = rl_point;
 193   orig_mark = rl_mark;
 194   last_found_line = orig_line = where_history ();
 195   reverse = direction < 0;
 196   hlist = history_list ();
 197   allocated_line = (char *)NULL;
 198
 199   isearch_terminators = _rl_isearch_terminators ? _rl_isearch_terminators
 200                                                 : default_isearch_terminators;
 201
 202   /* Create an arrary of pointers to the lines that we want to search. */
 203   rl_maybe_replace_line ();
 204   i = 0;
 205   if (hlist)
 206     for (i = 0; hlist[i]; i++);
 207
 208   /* Allocate space for this many lines, +1 for the current input line,
 209      and remember those lines. */
 210   lines = (char **)xmalloc ((1 + (hlen = i)) * sizeof (char *));
 211   for (i = 0; i < hlen; i++)
 212     lines[i] = hlist[i]->line;
 213
 214   if (_rl_saved_line_for_history)
 215     lines[i] = _rl_saved_line_for_history->line;
 216   else
 217     {
 218       /* Keep track of this so we can free it. */
 219       allocated_line = (char *)xmalloc (1 + strlen (rl_line_buffer));
 220       strcpy (allocated_line, &rl_line_buffer[0]);
 221       lines[i] = allocated_line;
 222     }
 223
 224   hlen++;
 225
 226   /* The line where we start the search. */
 227   i = orig_line;
 228
 229   rl_save_prompt ();
 230
 231   /* Initialize search parameters. */
 232   search_string = (char *)xmalloc (search_string_size = 128);
 233   *search_string = '\0';
 234   search_string_index = 0;
 235   prev_line_found = (char *)0;          /* XXX */
 236
 237   /* Normalize DIRECTION into 1 or -1. */
 238   direction = (direction >= 0) ? 1 : -1;
 239
 240   rl_display_search (search_string, reverse, -1);
 241
 242   sline = rl_line_buffer;
 243   sline_len = strlen (sline);
 244   line_index = rl_point;
 245
 246   found = failed = 0;
 247   for (;;)
 248     {
 249       rl_command_func_t *f = (rl_command_func_t *)NULL;
 250
 251       /* Read a key and decide how to proceed. */
 252       RL_SETSTATE(RL_STATE_MOREINPUT);
 253       c = rl_read_key ();
 254       RL_UNSETSTATE(RL_STATE_MOREINPUT);
 255
 256 #if defined (HANDLE_MULTIBYTE)
 257       if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 258         c = _rl_read_mbstring (c, mb, MB_LEN_MAX);
 259 #endif
 260
 261       /* Translate the keys we do something with to opcodes. */
 262       if (c >= 0 && _rl_keymap[c].type == ISFUNC)
 263         {
 264           f = _rl_keymap[c].function;
 265
 266           if (f == rl_reverse_search_history)
 267             c = reverse ? -1 : -2;
 268           else if (f == rl_forward_search_history)
 269             c =  !reverse ? -1 : -2;
 270           else if (f == rl_rubout)
 271             c = -3;
 272           else if (c == CTRL ('G'))
 273             c = -4;
 274           else if (c == CTRL ('W'))     /* XXX */
 275             c = -5;
 276           else if (c == CTRL ('Y'))     /* XXX */
 277             c = -6;
 278         }
 279
 280       /* The characters in isearch_terminators (set from the user-settable
 281          variable isearch-terminators) are used to terminate the search but
 282          not subsequently execute the character as a command.  The default
 283          value is "\033\012" (ESC and C-J). */
 284       if (strchr (isearch_terminators, c))
 285         {
 286           /* ESC still terminates the search, but if there is pending
 287              input or if input arrives within 0.1 seconds (on systems
 288              with select(2)) it is used as a prefix character
 289              with rl_execute_next.  WATCH OUT FOR THIS!  This is intended
 290              to allow the arrow keys to be used like ^F and ^B are used
 291              to terminate the search and execute the movement command.
 292              XXX - since _rl_input_available depends on the application-
 293              settable keyboard timeout value, this could alternatively
 294              use _rl_input_queued(100000) */
 295           if (c == ESC && _rl_input_available ())
 296             rl_execute_next (ESC);
 297           break;
 298         }
 299
 300 #define ENDSRCH_CHAR(c) \
 301   ((CTRL_CHAR (c) || META_CHAR (c) || (c) == RUBOUT) && ((c) != CTRL ('G')))
 302
 303 #if defined (HANDLE_MULTIBYTE)
 304       if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 305         {
 306           if (c >= 0 && strlen (mb) == 1 && ENDSRCH_CHAR (c))
 307             {
 308               /* This sets rl_pending_input to c; it will be picked up the next
 309                  time rl_read_key is called. */
 310               rl_execute_next (c);
 311               break;
 312             }
 313         }
 314       else
 315 #endif
 316       if (c >= 0 && ENDSRCH_CHAR (c))
 317         {
 318           /* This sets rl_pending_input to c; it will be picked up the next
 319              time rl_read_key is called. */
 320           rl_execute_next (c);
 321           break;
 322         }
 323
 324       switch (c)
 325         {
 326         case -1:
 327           if (search_string_index == 0)
 328             {
 329               if (last_isearch_string)
 330                 {
 331                   search_string_size = 64 + last_isearch_string_len;
 332                   search_string = (char *)xrealloc (search_string, search_string_size);
 333                   strcpy (search_string, last_isearch_string);
 334                   search_string_index = last_isearch_string_len;
 335                   rl_display_search (search_string, reverse, -1);
 336                   break;
 337                 }
 338               continue;
 339             }
 340           else if (reverse)
 341             --line_index;
 342           else if (line_index != sline_len)
 343             ++line_index;
 344           else
 345             rl_ding ();
 346           break;
 347
 348           /* switch directions */
 349         case -2:
 350           direction = -direction;
 351           reverse = direction < 0;
 352           break;
 353
 354         /* delete character from search string. */
 355         case -3:        /* C-H, DEL */
 356           /* This is tricky.  To do this right, we need to keep a
 357              stack of search positions for the current search, with
 358              sentinels marking the beginning and end.  But this will
 359              do until we have a real isearch-undo. */
 360           if (search_string_index == 0)
 361             rl_ding ();
 362           else
 363             search_string[--search_string_index] = '\0';
 364
 365           break;
 366
 367         case -4:        /* C-G */
 368           rl_replace_line (lines[orig_line], 0);
 369           rl_point = orig_point;
 370           rl_mark = orig_mark;
 371           rl_restore_prompt();
 372           rl_clear_message ();
 373           if (allocated_line)
 374             free (allocated_line);
 375           free (lines);
 376           RL_UNSETSTATE(RL_STATE_ISEARCH);
 377           return 0;
 378
 379         case -5:        /* C-W */
 380           /* skip over portion of line we already matched */
 381           wstart = rl_point + search_string_index;
 382           if (wstart >= rl_end)
 383             {
 384               rl_ding ();
 385               break;
 386             }
 387
 388           /* if not in a word, move to one. */
 389           if (rl_alphabetic(rl_line_buffer[wstart]) == 0)
 390             {
 391               rl_ding ();
 392               break;
 393             }
 394           n = wstart;
 395           while (n < rl_end && rl_alphabetic(rl_line_buffer[n]))
 396             n++;
 397           wlen = n - wstart + 1;
 398           if (search_string_index + wlen + 1 >= search_string_size)
 399             {
 400               search_string_size += wlen + 1;
 401               search_string = (char *)xrealloc (search_string, search_string_size);
 402             }
 403           for (; wstart < n; wstart++)
 404             search_string[search_string_index++] = rl_line_buffer[wstart];
 405           search_string[search_string_index] = '\0';
 406           break;
 407
 408         case -6:        /* C-Y */
 409           /* skip over portion of line we already matched */
 410           wstart = rl_point + search_string_index;
 411           if (wstart >= rl_end)
 412             {
 413               rl_ding ();
 414               break;
 415             }
 416           n = rl_end - wstart + 1;
 417           if (search_string_index + n + 1 >= search_string_size)
 418             {
 419               search_string_size += n + 1;
 420               search_string = (char *)xrealloc (search_string, search_string_size);
 421             }
 422           for (n = wstart; n < rl_end; n++)
 423             search_string[search_string_index++] = rl_line_buffer[n];
 424           search_string[search_string_index] = '\0';
 425           break;
 426
 427         default:
 428           /* Add character to search string and continue search. */
 429           if (search_string_index + 2 >= search_string_size)
 430             {
 431               search_string_size += 128;
 432               search_string = (char *)xrealloc (search_string, search_string_size);
 433             }
 434 #if defined (HANDLE_MULTIBYTE)
 435           if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 436             {
 437               int j, l;
 438               for (j = 0, l = strlen (mb); j < l; )
 439                 search_string[search_string_index++] = mb[j++];
 440             }
 441           else
 442 #endif
 443             search_string[search_string_index++] = c;
 444           search_string[search_string_index] = '\0';
 445           break;
 446         }
 447
 448       for (found = failed = 0;;)
 449         {
 450           int limit = sline_len - search_string_index + 1;
 451
 452           /* Search the current line. */
 453           while (reverse ? (line_index >= 0) : (line_index < limit))
 454             {
 455               if (STREQN (search_string, sline + line_index, search_string_index))
 456                 {
 457                   found++;
 458                   break;
 459                 }
 460               else
 461                 line_index += direction;
 462             }
 463           if (found)
 464             break;
 465
 466           /* Move to the next line, but skip new copies of the line
 467              we just found and lines shorter than the string we're
 468              searching for. */
 469           do
 470             {
 471               /* Move to the next line. */
 472               i += direction;
 473
 474               /* At limit for direction? */
 475               if (reverse ? (i < 0) : (i == hlen))
 476                 {
 477                   failed++;
 478                   break;
 479                 }
 480
 481               /* We will need these later. */
 482               sline = lines[i];
 483               sline_len = strlen (sline);
 484             }
 485           while ((prev_line_found && STREQ (prev_line_found, lines[i])) ||
 486                  (search_string_index > sline_len));
 487
 488           if (failed)
 489             break;
 490
 491           /* Now set up the line for searching... */
 492           line_index = reverse ? sline_len - search_string_index : 0;
 493         }
 494
 495       if (failed)
 496         {
 497           /* We cannot find the search string.  Ding the bell. */
 498           rl_ding ();
 499           i = last_found_line;
 500           continue;             /* XXX - was break */
 501         }
 502
 503       /* We have found the search string.  Just display it.  But don't
 504          actually move there in the history list until the user accepts
 505          the location. */
 506       if (found)
 507         {
 508           prev_line_found = lines[i];
 509           rl_replace_line (lines[i], 0);
 510           rl_point = line_index;
 511           last_found_line = i;
 512           rl_display_search (search_string, reverse, (i == orig_line) ? -1 : i);
 513         }
 514     }
 515
 516   /* The searching is over.  The user may have found the string that she
 517      was looking for, or else she may have exited a failing search.  If
 518      LINE_INDEX is -1, then that shows that the string searched for was
 519      not found.  We use this to determine where to place rl_point. */
 520
 521   /* First put back the original state. */
 522   strcpy (rl_line_buffer, lines[orig_line]);
 523
 524   rl_restore_prompt ();
 525
 526   /* Save the search string for possible later use. */
 527   FREE (last_isearch_string);
 528   last_isearch_string = search_string;
 529   last_isearch_string_len = search_string_index;
 530
 531   if (last_found_line < orig_line)
 532     rl_get_previous_history (orig_line - last_found_line, 0);
 533   else
 534     rl_get_next_history (last_found_line - orig_line, 0);
 535
 536   /* If the string was not found, put point at the end of the last matching
 537      line.  If last_found_line == orig_line, we didn't find any matching
 538      history lines at all, so put point back in its original position. */
 539   if (line_index < 0)
 540     {
 541       if (last_found_line == orig_line)
 542         line_index = orig_point;
 543       else
 544         line_index = strlen (rl_line_buffer);
 545       rl_mark = orig_mark;
 546     }
 547
 548   rl_point = line_index;
 549   /* Don't worry about where to put the mark here; rl_get_previous_history
 550      and rl_get_next_history take care of it. */
 551
 552   rl_clear_message ();
 553
 554   FREE (allocated_line);
 555   free (lines);
 556
 557   RL_UNSETSTATE(RL_STATE_ISEARCH);
 558
 559   return 0;
 560 }