readline/isearch.c

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