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