lib/readline/isearch.c

   1 /* isearch.c - incremental searching */
   2
   3 /* **************************************************************** */
   4 /*                                                                  */
   5 /*                      I-Search and Searching                      */
   6 /*                                                                  */
   7 /* **************************************************************** */
   8
   9 /* Copyright (C) 1987-2009 Free Software Foundation, Inc.
  10
  11    This file is part of the GNU Readline Library (Readline), a library
  12    for reading lines of text with interactive input and history editing.
  13
  14    Readline is free software: you can redistribute it and/or modify
  15    it under the terms of the GNU General Public License as published by
  16    the Free Software Foundation, either version 3 of the License, or
  17    (at your option) any later version.
  18
  19    Readline is distributed in the hope that it will be useful,
  20    but WITHOUT ANY WARRANTY; without even the implied warranty of
  21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22    GNU General Public License for more details.
  23
  24    You should have received a copy of the GNU General Public License
  25    along with Readline.  If not, see <http://www.gnu.org/licenses/>.
  26 */
  27
  28 #define READLINE_LIBRARY
  29
  30 #if defined (HAVE_CONFIG_H)
  31 #  include <config.h>
  32 #endif
  33
  34 #include <sys/types.h>
  35
  36 #include <stdio.h>
  37
  38 #if defined (HAVE_UNISTD_H)
  39 #  include <unistd.h>
  40 #endif
  41
  42 #if defined (HAVE_STDLIB_H)
  43 #  include <stdlib.h>
  44 #else
  45 #  include "ansi_stdlib.h"
  46 #endif
  47
  48 #include "rldefs.h"
  49 #include "rlmbutil.h"
  50
  51 #include "readline.h"
  52 #include "history.h"
  53
  54 #include "rlprivate.h"
  55 #include "xmalloc.h"
  56
  57 /* Variables exported to other files in the readline library. */
  58 char *_rl_isearch_terminators = (char *)NULL;
  59
  60 _rl_search_cxt *_rl_iscxt = 0;
  61
  62 /* Variables imported from other files in the readline library. */
  63 extern HIST_ENTRY *_rl_saved_line_for_history;
  64
  65 static int rl_search_history PARAMS((int, int));
  66
  67 static _rl_search_cxt *_rl_isearch_init PARAMS((int));
  68 static void _rl_isearch_fini PARAMS((_rl_search_cxt *));
  69 static int _rl_isearch_cleanup PARAMS((_rl_search_cxt *, int));
  70
  71 /* Last line found by the current incremental search, so we don't `find'
  72    identical lines many times in a row.  Now part of isearch context. */
  73 /* static char *prev_line_found; */
  74
  75 /* Last search string and its length. */
  76 static char *last_isearch_string;
  77 static int last_isearch_string_len;
  78
  79 static char * const default_isearch_terminators = "\033\012";
  80
  81 _rl_search_cxt *
  82 _rl_scxt_alloc (type, flags)
  83      int type, flags;
  84 {
  85   _rl_search_cxt *cxt;
  86
  87   cxt = (_rl_search_cxt *)xmalloc (sizeof (_rl_search_cxt));
  88
  89   cxt->type = type;
  90   cxt->sflags = flags;
  91
  92   cxt->search_string = 0;
  93   cxt->search_string_size = cxt->search_string_index = 0;
  94
  95   cxt->lines = 0;
  96   cxt->allocated_line = 0;
  97   cxt->hlen = cxt->hindex = 0;
  98
  99   cxt->save_point = rl_point;
 100   cxt->save_mark = rl_mark;
 101   cxt->save_line = where_history ();
 102   cxt->last_found_line = cxt->save_line;
 103   cxt->prev_line_found = 0;
 104
 105   cxt->save_undo_list = 0;
 106
 107   cxt->history_pos = 0;
 108   cxt->direction = 0;
 109
 110   cxt->lastc = 0;
 111
 112   cxt->sline = 0;
 113   cxt->sline_len = cxt->sline_index = 0;
 114
 115   cxt->search_terminators = 0;
 116
 117   return cxt;
 118 }
 119
 120 void
 121 _rl_scxt_dispose (cxt, flags)
 122      _rl_search_cxt *cxt;
 123      int flags;
 124 {
 125   FREE (cxt->search_string);
 126   FREE (cxt->allocated_line);
 127   FREE (cxt->lines);
 128
 129   xfree (cxt);
 130 }
 131
 132 /* Search backwards through the history looking for a string which is typed
 133    interactively.  Start with the current line. */
 134 int
 135 rl_reverse_search_history (sign, key)
 136      int sign, key;
 137 {
 138   return (rl_search_history (-sign, key));
 139 }
 140
 141 /* Search forwards through the history looking for a string which is typed
 142    interactively.  Start with the current line. */
 143 int
 144 rl_forward_search_history (sign, key)
 145      int sign, key;
 146 {
 147   return (rl_search_history (sign, key));
 148 }
 149
 150 /* Display the current state of the search in the echo-area.
 151    SEARCH_STRING contains the string that is being searched for,
 152    DIRECTION is zero for forward, or non-zero for reverse,
 153    WHERE is the history list number of the current line.  If it is
 154    -1, then this line is the starting one. */
 155 static void
 156 rl_display_search (search_string, reverse_p, where)
 157      char *search_string;
 158      int reverse_p, where;
 159 {
 160   char *message;
 161   int msglen, searchlen;
 162
 163   searchlen = (search_string && *search_string) ? strlen (search_string) : 0;
 164
 165   message = (char *)xmalloc (searchlen + 33);
 166   msglen = 0;
 167
 168 #if defined (NOTDEF)
 169   if (where != -1)
 170     {
 171       sprintf (message, "[%d]", where + history_base);
 172       msglen = strlen (message);
 173     }
 174 #endif /* NOTDEF */
 175
 176   message[msglen++] = '(';
 177
 178   if (reverse_p)
 179     {
 180       strcpy (message + msglen, "reverse-");
 181       msglen += 8;
 182     }
 183
 184   strcpy (message + msglen, "i-search)`");
 185   msglen += 10;
 186
 187   if (search_string)
 188     {
 189       strcpy (message + msglen, search_string);
 190       msglen += searchlen;
 191     }
 192
 193   strcpy (message + msglen, "': ");
 194
 195   rl_message ("%s", message);
 196   xfree (message);
 197   (*rl_redisplay_function) ();
 198 }
 199
 200 static _rl_search_cxt *
 201 _rl_isearch_init (direction)
 202      int direction;
 203 {
 204   _rl_search_cxt *cxt;
 205   register int i;
 206   HIST_ENTRY **hlist;
 207
 208   cxt = _rl_scxt_alloc (RL_SEARCH_ISEARCH, 0);
 209   if (direction < 0)
 210     cxt->sflags |= SF_REVERSE;
 211
 212   cxt->search_terminators = _rl_isearch_terminators ? _rl_isearch_terminators
 213                                                 : default_isearch_terminators;
 214
 215   /* Create an arrary of pointers to the lines that we want to search. */
 216   hlist = history_list ();
 217   rl_maybe_replace_line ();
 218   i = 0;
 219   if (hlist)
 220     for (i = 0; hlist[i]; i++);
 221
 222   /* Allocate space for this many lines, +1 for the current input line,
 223      and remember those lines. */
 224   cxt->lines = (char **)xmalloc ((1 + (cxt->hlen = i)) * sizeof (char *));
 225   for (i = 0; i < cxt->hlen; i++)
 226     cxt->lines[i] = hlist[i]->line;
 227
 228   if (_rl_saved_line_for_history)
 229     cxt->lines[i] = _rl_saved_line_for_history->line;
 230   else
 231     {
 232       /* Keep track of this so we can free it. */
 233       cxt->allocated_line = (char *)xmalloc (1 + strlen (rl_line_buffer));
 234       strcpy (cxt->allocated_line, &rl_line_buffer[0]);
 235       cxt->lines[i] = cxt->allocated_line;
 236     }
 237
 238   cxt->hlen++;
 239
 240   /* The line where we start the search. */
 241   cxt->history_pos = cxt->save_line;
 242
 243   rl_save_prompt ();
 244
 245   /* Initialize search parameters. */
 246   cxt->search_string = (char *)xmalloc (cxt->search_string_size = 128);
 247   cxt->search_string[cxt->search_string_index = 0] = '\0';
 248
 249   /* Normalize DIRECTION into 1 or -1. */
 250   cxt->direction = (direction >= 0) ? 1 : -1;
 251
 252   cxt->sline = rl_line_buffer;
 253   cxt->sline_len = strlen (cxt->sline);
 254   cxt->sline_index = rl_point;
 255
 256   _rl_iscxt = cxt;              /* save globally */
 257
 258   return cxt;
 259 }
 260
 261 static void
 262 _rl_isearch_fini (cxt)
 263      _rl_search_cxt *cxt;
 264 {
 265   /* First put back the original state. */
 266   strcpy (rl_line_buffer, cxt->lines[cxt->save_line]);
 267
 268   rl_restore_prompt ();
 269
 270   /* Save the search string for possible later use. */
 271   FREE (last_isearch_string);
 272   last_isearch_string = cxt->search_string;
 273   last_isearch_string_len = cxt->search_string_index;
 274   cxt->search_string = 0;
 275
 276   if (cxt->last_found_line < cxt->save_line)
 277     rl_get_previous_history (cxt->save_line - cxt->last_found_line, 0);
 278   else
 279     rl_get_next_history (cxt->last_found_line - cxt->save_line, 0);
 280
 281   /* If the string was not found, put point at the end of the last matching
 282      line.  If last_found_line == orig_line, we didn't find any matching
 283      history lines at all, so put point back in its original position. */
 284   if (cxt->sline_index < 0)
 285     {
 286       if (cxt->last_found_line == cxt->save_line)
 287         cxt->sline_index = cxt->save_point;
 288       else
 289         cxt->sline_index = strlen (rl_line_buffer);
 290       rl_mark = cxt->save_mark;
 291     }
 292
 293   rl_point = cxt->sline_index;
 294   /* Don't worry about where to put the mark here; rl_get_previous_history
 295      and rl_get_next_history take care of it. */
 296
 297   rl_clear_message ();
 298 }
 299
 300 int
 301 _rl_search_getchar (cxt)
 302      _rl_search_cxt *cxt;
 303 {
 304   int c;
 305
 306   /* Read a key and decide how to proceed. */
 307   RL_SETSTATE(RL_STATE_MOREINPUT);
 308   c = cxt->lastc = rl_read_key ();
 309   RL_UNSETSTATE(RL_STATE_MOREINPUT);
 310
 311 #if defined (HANDLE_MULTIBYTE)
 312   if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 313     c = cxt->lastc = _rl_read_mbstring (cxt->lastc, cxt->mb, MB_LEN_MAX);
 314 #endif
 315
 316   return c;
 317 }
 318
 319 /* Process just-read character C according to isearch context CXT.  Return
 320    -1 if the caller should just free the context and return, 0 if we should
 321    break out of the loop, and 1 if we should continue to read characters. */
 322 int
 323 _rl_isearch_dispatch (cxt, c)
 324      _rl_search_cxt *cxt;
 325      int c;
 326 {
 327   int n, wstart, wlen, limit, cval;
 328   rl_command_func_t *f;
 329
 330   f = (rl_command_func_t *)NULL;
 331
 332   if (c < 0)
 333     {
 334       cxt->sflags |= SF_FAILED;
 335       cxt->history_pos = cxt->last_found_line;
 336       return -1;
 337     }
 338
 339   /* Translate the keys we do something with to opcodes. */
 340   if (c >= 0 && _rl_keymap[c].type == ISFUNC)
 341     {
 342       f = _rl_keymap[c].function;
 343
 344       if (f == rl_reverse_search_history)
 345         cxt->lastc = (cxt->sflags & SF_REVERSE) ? -1 : -2;
 346       else if (f == rl_forward_search_history)
 347         cxt->lastc = (cxt->sflags & SF_REVERSE) ? -2 : -1;
 348       else if (f == rl_rubout)
 349         cxt->lastc = -3;
 350       else if (c == CTRL ('G'))
 351         cxt->lastc = -4;
 352       else if (c == CTRL ('W')) /* XXX */
 353         cxt->lastc = -5;
 354       else if (c == CTRL ('Y')) /* XXX */
 355         cxt->lastc = -6;
 356     }
 357
 358   /* The characters in isearch_terminators (set from the user-settable
 359      variable isearch-terminators) are used to terminate the search but
 360      not subsequently execute the character as a command.  The default
 361      value is "\033\012" (ESC and C-J). */
 362   if (strchr (cxt->search_terminators, cxt->lastc))
 363     {
 364       /* ESC still terminates the search, but if there is pending
 365          input or if input arrives within 0.1 seconds (on systems
 366          with select(2)) it is used as a prefix character
 367          with rl_execute_next.  WATCH OUT FOR THIS!  This is intended
 368          to allow the arrow keys to be used like ^F and ^B are used
 369          to terminate the search and execute the movement command.
 370          XXX - since _rl_input_available depends on the application-
 371          settable keyboard timeout value, this could alternatively
 372          use _rl_input_queued(100000) */
 373       if (cxt->lastc == ESC && _rl_input_available ())
 374         rl_execute_next (ESC);
 375       return (0);
 376     }
 377
 378 #define ENDSRCH_CHAR(c) \
 379   ((CTRL_CHAR (c) || META_CHAR (c) || (c) == RUBOUT) && ((c) != CTRL ('G')))
 380
 381 #if defined (HANDLE_MULTIBYTE)
 382   if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 383     {
 384       if (cxt->lastc >= 0 && (cxt->mb[0] && cxt->mb[1] == '\0') && ENDSRCH_CHAR (cxt->lastc))
 385         {
 386           /* This sets rl_pending_input to c; it will be picked up the next
 387              time rl_read_key is called. */
 388           rl_execute_next (cxt->lastc);
 389           return (0);
 390         }
 391     }
 392   else
 393 #endif
 394     if (cxt->lastc >= 0 && ENDSRCH_CHAR (cxt->lastc))
 395       {
 396         /* This sets rl_pending_input to LASTC; it will be picked up the next
 397            time rl_read_key is called. */
 398         rl_execute_next (cxt->lastc);
 399         return (0);
 400       }
 401
 402   /* Now dispatch on the character.  `Opcodes' affect the search string or
 403      state.  Other characters are added to the string.  */
 404   switch (cxt->lastc)
 405     {
 406     /* search again */
 407     case -1:
 408       if (cxt->search_string_index == 0)
 409         {
 410           if (last_isearch_string)
 411             {
 412               cxt->search_string_size = 64 + last_isearch_string_len;
 413               cxt->search_string = (char *)xrealloc (cxt->search_string, cxt->search_string_size);
 414               strcpy (cxt->search_string, last_isearch_string);
 415               cxt->search_string_index = last_isearch_string_len;
 416               rl_display_search (cxt->search_string, (cxt->sflags & SF_REVERSE), -1);
 417               break;
 418             }
 419           return (1);
 420         }
 421       else if (cxt->sflags & SF_REVERSE)
 422         cxt->sline_index--;
 423       else if (cxt->sline_index != cxt->sline_len)
 424         cxt->sline_index++;
 425       else
 426         rl_ding ();
 427       break;
 428
 429     /* switch directions */
 430     case -2:
 431       cxt->direction = -cxt->direction;
 432       if (cxt->direction < 0)
 433         cxt->sflags |= SF_REVERSE;
 434       else
 435         cxt->sflags &= ~SF_REVERSE;
 436       break;
 437
 438     /* delete character from search string. */
 439     case -3:    /* C-H, DEL */
 440       /* This is tricky.  To do this right, we need to keep a
 441          stack of search positions for the current search, with
 442          sentinels marking the beginning and end.  But this will
 443          do until we have a real isearch-undo. */
 444       if (cxt->search_string_index == 0)
 445         rl_ding ();
 446       else
 447         cxt->search_string[--cxt->search_string_index] = '\0';
 448       break;
 449
 450     case -4:    /* C-G, abort */
 451       rl_replace_line (cxt->lines[cxt->save_line], 0);
 452       rl_point = cxt->save_point;
 453       rl_mark = cxt->save_mark;
 454       rl_restore_prompt();
 455       rl_clear_message ();
 456
 457       return -1;
 458
 459     case -5:    /* C-W */
 460       /* skip over portion of line we already matched and yank word */
 461       wstart = rl_point + cxt->search_string_index;
 462       if (wstart >= rl_end)
 463         {
 464           rl_ding ();
 465           break;
 466         }
 467
 468       /* if not in a word, move to one. */
 469       cval = _rl_char_value (rl_line_buffer, wstart);
 470       if (_rl_walphabetic (cval) == 0)
 471         {
 472           rl_ding ();
 473           break;
 474         }
 475       n = MB_NEXTCHAR (rl_line_buffer, wstart, 1, MB_FIND_NONZERO);;
 476       while (n < rl_end)
 477         {
 478           cval = _rl_char_value (rl_line_buffer, n);
 479           if (_rl_walphabetic (cval) == 0)
 480             break;
 481           n = MB_NEXTCHAR (rl_line_buffer, n, 1, MB_FIND_NONZERO);;
 482         }
 483       wlen = n - wstart + 1;
 484       if (cxt->search_string_index + wlen + 1 >= cxt->search_string_size)
 485         {
 486           cxt->search_string_size += wlen + 1;
 487           cxt->search_string = (char *)xrealloc (cxt->search_string, cxt->search_string_size);
 488         }
 489       for (; wstart < n; wstart++)
 490         cxt->search_string[cxt->search_string_index++] = rl_line_buffer[wstart];
 491       cxt->search_string[cxt->search_string_index] = '\0';
 492       break;
 493
 494     case -6:    /* C-Y */
 495       /* skip over portion of line we already matched and yank rest */
 496       wstart = rl_point + cxt->search_string_index;
 497       if (wstart >= rl_end)
 498         {
 499           rl_ding ();
 500           break;
 501         }
 502       n = rl_end - wstart + 1;
 503       if (cxt->search_string_index + n + 1 >= cxt->search_string_size)
 504         {
 505           cxt->search_string_size += n + 1;
 506           cxt->search_string = (char *)xrealloc (cxt->search_string, cxt->search_string_size);
 507         }
 508       for (n = wstart; n < rl_end; n++)
 509         cxt->search_string[cxt->search_string_index++] = rl_line_buffer[n];
 510       cxt->search_string[cxt->search_string_index] = '\0';
 511       break;
 512
 513     /* Add character to search string and continue search. */
 514     default:
 515       if (cxt->search_string_index + 2 >= cxt->search_string_size)
 516         {
 517           cxt->search_string_size += 128;
 518           cxt->search_string = (char *)xrealloc (cxt->search_string, cxt->search_string_size);
 519         }
 520 #if defined (HANDLE_MULTIBYTE)
 521       if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)
 522         {
 523           int j, l;
 524           for (j = 0, l = strlen (cxt->mb); j < l; )
 525             cxt->search_string[cxt->search_string_index++] = cxt->mb[j++];
 526         }
 527       else
 528 #endif
 529         cxt->search_string[cxt->search_string_index++] = c;
 530       cxt->search_string[cxt->search_string_index] = '\0';
 531       break;
 532     }
 533
 534   for (cxt->sflags &= ~(SF_FOUND|SF_FAILED);; )
 535     {
 536       limit = cxt->sline_len - cxt->search_string_index + 1;
 537
 538       /* Search the current line. */
 539       while ((cxt->sflags & SF_REVERSE) ? (cxt->sline_index >= 0) : (cxt->sline_index < limit))
 540         {
 541           if (STREQN (cxt->search_string, cxt->sline + cxt->sline_index, cxt->search_string_index))
 542             {
 543               cxt->sflags |= SF_FOUND;
 544               break;
 545             }
 546           else
 547             cxt->sline_index += cxt->direction;
 548         }
 549       if (cxt->sflags & SF_FOUND)
 550         break;
 551
 552       /* Move to the next line, but skip new copies of the line
 553          we just found and lines shorter than the string we're
 554          searching for. */
 555       do
 556         {
 557           /* Move to the next line. */
 558           cxt->history_pos += cxt->direction;
 559
 560           /* At limit for direction? */
 561           if ((cxt->sflags & SF_REVERSE) ? (cxt->history_pos < 0) : (cxt->history_pos == cxt->hlen))
 562             {
 563               cxt->sflags |= SF_FAILED;
 564               break;
 565             }
 566
 567           /* We will need these later. */
 568           cxt->sline = cxt->lines[cxt->history_pos];
 569           cxt->sline_len = strlen (cxt->sline);
 570         }
 571       while ((cxt->prev_line_found && STREQ (cxt->prev_line_found, cxt->lines[cxt->history_pos])) ||
 572              (cxt->search_string_index > cxt->sline_len));
 573
 574       if (cxt->sflags & SF_FAILED)
 575         break;
 576
 577       /* Now set up the line for searching... */
 578       cxt->sline_index = (cxt->sflags & SF_REVERSE) ? cxt->sline_len - cxt->search_string_index : 0;
 579     }
 580
 581   if (cxt->sflags & SF_FAILED)
 582     {
 583       /* We cannot find the search string.  Ding the bell. */
 584       rl_ding ();
 585       cxt->history_pos = cxt->last_found_line;
 586       return 1;
 587     }
 588
 589   /* We have found the search string.  Just display it.  But don't
 590      actually move there in the history list until the user accepts
 591      the location. */
 592   if (cxt->sflags & SF_FOUND)
 593     {
 594       cxt->prev_line_found = cxt->lines[cxt->history_pos];
 595       rl_replace_line (cxt->lines[cxt->history_pos], 0);
 596       rl_point = cxt->sline_index;
 597       cxt->last_found_line = cxt->history_pos;
 598       rl_display_search (cxt->search_string, (cxt->sflags & SF_REVERSE), (cxt->history_pos == cxt->save_line) ? -1 : cxt->history_pos);
 599     }
 600
 601   return 1;
 602 }
 603
 604 static int
 605 _rl_isearch_cleanup (cxt, r)
 606      _rl_search_cxt *cxt;
 607      int r;
 608 {
 609   if (r >= 0)
 610     _rl_isearch_fini (cxt);
 611   _rl_scxt_dispose (cxt, 0);
 612   _rl_iscxt = 0;
 613
 614   RL_UNSETSTATE(RL_STATE_ISEARCH);
 615
 616   return (r != 0);
 617 }
 618
 619 /* Search through the history looking for an interactively typed string.
 620    This is analogous to i-search.  We start the search in the current line.
 621    DIRECTION is which direction to search; >= 0 means forward, < 0 means
 622    backwards. */
 623 static int
 624 rl_search_history (direction, invoking_key)
 625      int direction, invoking_key;
 626 {
 627   _rl_search_cxt *cxt;          /* local for now, but saved globally */
 628   int c, r;
 629
 630   RL_SETSTATE(RL_STATE_ISEARCH);
 631   cxt = _rl_isearch_init (direction);
 632
 633   rl_display_search (cxt->search_string, (cxt->sflags & SF_REVERSE), -1);
 634
 635   /* If we are using the callback interface, all we do is set up here and
 636       return.  The key is that we leave RL_STATE_ISEARCH set. */
 637   if (RL_ISSTATE (RL_STATE_CALLBACK))
 638     return (0);
 639
 640   r = -1;
 641   for (;;)
 642     {
 643       c = _rl_search_getchar (cxt);
 644       /* We might want to handle EOF here (c == 0) */
 645       r = _rl_isearch_dispatch (cxt, cxt->lastc);
 646       if (r <= 0)
 647         break;
 648     }
 649
 650   /* The searching is over.  The user may have found the string that she
 651      was looking for, or else she may have exited a failing search.  If
 652      LINE_INDEX is -1, then that shows that the string searched for was
 653      not found.  We use this to determine where to place rl_point. */
 654   return (_rl_isearch_cleanup (cxt, r));
 655 }
 656
 657 #if defined (READLINE_CALLBACKS)
 658 /* Called from the callback functions when we are ready to read a key.  The
 659    callback functions know to call this because RL_ISSTATE(RL_STATE_ISEARCH).
 660    If _rl_isearch_dispatch finishes searching, this function is responsible
 661    for turning off RL_STATE_ISEARCH, which it does using _rl_isearch_cleanup. */
 662 int
 663 _rl_isearch_callback (cxt)
 664      _rl_search_cxt *cxt;
 665 {
 666   int c, r;
 667
 668   c = _rl_search_getchar (cxt);
 669   /* We might want to handle EOF here */
 670   r = _rl_isearch_dispatch (cxt, cxt->lastc);
 671
 672   return (r <= 0) ? _rl_isearch_cleanup (cxt, r) : 0;
 673 }
 674 #endif