readline/history.c

   1 /* History.c -- standalone history library */
   2
   3 /* Copyright (C) 1989, 1991 Free Software Foundation, Inc.
   4
   5    This file contains the GNU History Library (the Library), a set of
   6    routines for managing the text of previously typed lines.
   7
   8    The Library is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    The Library is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21
  22 /* The goal is to make the implementation transparent, so that you
  23    don't have to know what data types are used, just what functions
  24    you can call.  I think I have done that. */
  25
  26 /* Remove these declarations when we have a complete libgnu.a. */
  27 #if !defined (STATIC_MALLOC)
  28 extern char *xmalloc (), *xrealloc ();
  29 #else
  30 static char *xmalloc (), *xrealloc ();
  31 #endif
  32
  33 #include "sysdep.h"
  34 #include <stdio.h>
  35 #include <errno.h>
  36 #include <sys/types.h>
  37 #ifndef NO_SYS_FILE
  38 #include <sys/file.h>
  39 #endif
  40 #include <sys/stat.h>
  41 #include <fcntl.h>
  42
  43 #include "history.h"
  44
  45 #ifndef savestring
  46 #define savestring(x) (char *)strcpy (xmalloc (1 + strlen (x)), (x))
  47 #endif
  48
  49 #ifndef whitespace
  50 #define whitespace(c) (((c) == ' ') || ((c) == '\t'))
  51 #endif
  52
  53 #ifndef digit
  54 #define digit(c)  ((c) >= '0' && (c) <= '9')
  55 #endif
  56
  57 #ifndef member
  58 #define member(c, s) ((c) ? index ((s), (c)) : 0)
  59 #endif
  60
  61 /* **************************************************************** */
  62 /*                                                                  */
  63 /*                      History Functions                           */
  64 /*                                                                  */
  65 /* **************************************************************** */
  66
  67 /* An array of HIST_ENTRY.  This is where we store the history. */
  68 static HIST_ENTRY **the_history = (HIST_ENTRY **)NULL;
  69
  70 /* Non-zero means that we have enforced a limit on the amount of
  71    history that we save. */
  72 int history_stifled = 0;
  73
  74 /* If HISTORY_STIFLED is non-zero, then this is the maximum number of
  75    entries to remember. */
  76 int max_input_history;
  77
  78 /* The current location of the interactive history pointer.  Just makes
  79    life easier for outside callers. */
  80 static int history_offset = 0;
  81
  82 /* The number of strings currently stored in the input_history list. */
  83 int history_length = 0;
  84
  85 /* The current number of slots allocated to the input_history. */
  86 static int history_size = 0;
  87
  88 /* The number of slots to increase the_history by. */
  89 #define DEFAULT_HISTORY_GROW_SIZE 50
  90
  91 /* The character that represents the start of a history expansion
  92    request.  This is usually `!'. */
  93 char history_expansion_char = '!';
  94
  95 /* The character that invokes word substitution if found at the start of
  96    a line.  This is usually `^'. */
  97 char history_subst_char = '^';
  98
  99 /* During tokenization, if this character is seen as the first character
 100    of a word, then it, and all subsequent characters upto a newline are
 101    ignored.  For a Bourne shell, this should be '#'.  Bash special cases
 102    the interactive comment character to not be a comment delimiter. */
 103 char history_comment_char = '\0';
 104
 105 /* The list of characters which inhibit the expansion of text if found
 106    immediately following history_expansion_char. */
 107 char *history_no_expand_chars = " \t\n\r=";
 108
 109 /* The logical `base' of the history array.  It defaults to 1. */
 110 int history_base = 1;
 111
 112 /* Begin a session in which the history functions might be used.  This
 113    initializes interactive variables. */
 114 void
 115 using_history ()
 116 {
 117   history_offset = history_length;
 118 }
 119
 120 /* Return the number of bytes that the primary history entries are using.
 121    This just adds up the lengths of the_history->lines. */
 122 int
 123 history_total_bytes ()
 124 {
 125   register int i, result;
 126
 127   result = 0;
 128
 129   for (i = 0; the_history && the_history[i]; i++)
 130     result += strlen (the_history[i]->line);
 131
 132   return (result);
 133 }
 134
 135 /* Place STRING at the end of the history list.  The data field
 136    is  set to NULL. */
 137 void
 138 add_history (string)
 139      char *string;
 140 {
 141   HIST_ENTRY *temp;
 142
 143   if (history_stifled && (history_length == max_input_history))
 144     {
 145       register int i;
 146
 147       /* If the history is stifled, and history_length is zero,
 148          and it equals max_input_history, we don't save items. */
 149       if (!history_length)
 150         return;
 151
 152       /* If there is something in the slot, then remove it. */
 153       if (the_history[0])
 154         {
 155           free (the_history[0]->line);
 156           free (the_history[0]);
 157         }
 158
 159       for (i = 0; i < history_length; i++)
 160         the_history[i] = the_history[i + 1];
 161
 162       history_base++;
 163
 164     }
 165   else
 166     {
 167       if (!history_size)
 168         {
 169           the_history = (HIST_ENTRY **)
 170             xmalloc ((history_size = DEFAULT_HISTORY_GROW_SIZE)
 171                      * sizeof (HIST_ENTRY *));
 172           history_length = 1;
 173
 174         }
 175       else
 176         {
 177           if (history_length == (history_size - 1))
 178             {
 179               the_history = (HIST_ENTRY **)
 180                 xrealloc (the_history,
 181                           ((history_size += DEFAULT_HISTORY_GROW_SIZE)
 182                            * sizeof (HIST_ENTRY *)));
 183           }
 184           history_length++;
 185         }
 186     }
 187
 188   temp = (HIST_ENTRY *)xmalloc (sizeof (HIST_ENTRY));
 189   temp->line = savestring (string);
 190   temp->data = (char *)NULL;
 191
 192   the_history[history_length] = (HIST_ENTRY *)NULL;
 193   the_history[history_length - 1] = temp;
 194 }
 195
 196 /* Make the history entry at WHICH have LINE and DATA.  This returns
 197    the old entry so you can dispose of the data.  In the case of an
 198    invalid WHICH, a NULL pointer is returned. */
 199 HIST_ENTRY *
 200 replace_history_entry (which, line, data)
 201      int which;
 202      char *line;
 203      char *data;
 204 {
 205   HIST_ENTRY *temp = (HIST_ENTRY *)xmalloc (sizeof (HIST_ENTRY));
 206   HIST_ENTRY *old_value;
 207
 208   if (which >= history_length)
 209     return ((HIST_ENTRY *)NULL);
 210
 211   old_value = the_history[which];
 212
 213   temp->line = savestring (line);
 214   temp->data = data;
 215   the_history[which] = temp;
 216
 217   return (old_value);
 218 }
 219
 220 /* Returns the magic number which says what history element we are
 221    looking at now.  In this implementation, it returns history_offset. */
 222 int
 223 where_history ()
 224 {
 225   return (history_offset);
 226 }
 227
 228 /* Search the history for STRING, starting at history_offset.
 229    If DIRECTION < 0, then the search is through previous entries, else
 230    through subsequent.  If ANCHORED is non-zero, the string must
 231    appear at the beginning of a history line, otherwise, the string
 232    may appear anywhere in the line.  If the string is found, then
 233    current_history () is the history entry, and the value of this
 234    function is the offset in the line of that history entry that the
 235    string was found in.  Otherwise, nothing is changed, and a -1 is
 236    returned. */
 237
 238 #define ANCHORED_SEARCH 1
 239 #define NON_ANCHORED_SEARCH 0
 240
 241 static int
 242 history_search_internal (string, direction, anchored)
 243      char *string;
 244      int direction, anchored;
 245 {
 246   register int i = history_offset;
 247   register int reverse = (direction < 0);
 248   register char *line;
 249   register int index;
 250   int string_len = strlen (string);
 251
 252   /* Take care of trivial cases first. */
 253
 254   if (!history_length || ((i == history_length) && !reverse))
 255     return (-1);
 256
 257   if (reverse && (i == history_length))
 258     i--;
 259
 260   while (1)
 261     {
 262       /* Search each line in the history list for STRING. */
 263
 264       /* At limit for direction? */
 265       if ((reverse && i < 0) ||
 266           (!reverse && i == history_length))
 267         return (-1);
 268
 269       line = the_history[i]->line;
 270       index = strlen (line);
 271
 272       /* If STRING is longer than line, no match. */
 273       if (string_len > index)
 274         goto next_line;
 275
 276       /* Handle anchored searches first. */
 277       if (anchored == ANCHORED_SEARCH)
 278         {
 279           if (strncmp (string, line, string_len) == 0)
 280             {
 281               history_offset = i;
 282               return (0);
 283             }
 284
 285           goto next_line;
 286         }
 287
 288       /* Do substring search. */
 289       if (reverse)
 290         {
 291           index -= string_len;
 292
 293           while (index >= 0)
 294             {
 295               if (strncmp (string, line + index, string_len) == 0)
 296                 {
 297                   history_offset = i;
 298                   return (index);
 299                 }
 300               index--;
 301             }
 302         }
 303       else
 304         {
 305           register int limit = index - string_len + 1;
 306           index = 0;
 307
 308           while (index < limit)
 309             {
 310               if (strncmp (string, line + index, string_len) == 0)
 311                 {
 312                   history_offset = i;
 313                   return (index);
 314                 }
 315               index++;
 316             }
 317         }
 318     next_line:
 319       if (reverse)
 320         i--;
 321       else
 322         i++;
 323     }
 324 }
 325
 326 /* Do a non-anchored search for STRING through the history in DIRECTION. */
 327 int
 328 history_search (string, direction)
 329      char *string;
 330      int direction;
 331 {
 332   return (history_search_internal (string, direction, NON_ANCHORED_SEARCH));
 333 }
 334
 335 /* Do an anchored search for string through the history in DIRECTION. */
 336 int
 337 history_search_prefix (string, direction)
 338      char *string;
 339      int direction;
 340 {
 341   return (history_search_internal (string, direction, ANCHORED_SEARCH));
 342 }
 343
 344 /* Remove history element WHICH from the history.  The removed
 345    element is returned to you so you can free the line, data,
 346    and containing structure. */
 347 HIST_ENTRY *
 348 remove_history (which)
 349      int which;
 350 {
 351   HIST_ENTRY *return_value;
 352
 353   if (which >= history_length || !history_length)
 354     return_value = (HIST_ENTRY *)NULL;
 355   else
 356     {
 357       register int i;
 358       return_value = the_history[which];
 359
 360       for (i = which; i < history_length; i++)
 361         the_history[i] = the_history[i + 1];
 362
 363       history_length--;
 364     }
 365
 366   return (return_value);
 367 }
 368
 369 /* Stifle the history list, remembering only MAX number of lines. */
 370 void
 371 stifle_history (max)
 372      int max;
 373 {
 374   if (history_length > max)
 375     {
 376       register int i, j;
 377
 378       /* This loses because we cannot free the data. */
 379       for (i = 0; i < (history_length - max); i++)
 380         {
 381           free (the_history[i]->line);
 382           free (the_history[i]);
 383         }
 384       history_base = i;
 385       for (j = 0, i = history_length - max; j < max; i++, j++)
 386         the_history[j] = the_history[i];
 387       the_history[j] = (HIST_ENTRY *)NULL;
 388       history_length = j;
 389     }
 390   history_stifled = 1;
 391   max_input_history = max;
 392 }
 393
 394 /* Stop stifling the history.  This returns the previous amount the history
 395  was stifled by.  The value is positive if the history was stifled, negative
 396  if it wasn't. */
 397 int
 398 unstifle_history ()
 399 {
 400   int result = max_input_history;
 401   if (history_stifled)
 402     {
 403       result = - result;
 404       history_stifled = 0;
 405     }
 406   return (result);
 407 }
 408
 409 /* Return the string that should be used in the place of this
 410    filename.  This only matters when you don't specify the
 411    filename to read_history (), or write_history (). */
 412 static char *
 413 history_filename (filename)
 414      char *filename;
 415 {
 416   char *return_val = filename ? savestring (filename) : (char *)NULL;
 417
 418   if (!return_val)
 419     {
 420       char *home = (char *)getenv ("HOME");
 421       if (!home) home = ".";
 422       return_val = (char *)xmalloc (2 + strlen (home) + strlen (".history"));
 423       sprintf (return_val, "%s/.history", home);
 424     }
 425   return (return_val);
 426 }
 427
 428 /* Add the contents of FILENAME to the history list, a line at a time.
 429    If FILENAME is NULL, then read from ~/.history.  Returns 0 if
 430    successful, or errno if not. */
 431 int
 432 read_history (filename)
 433      char *filename;
 434 {
 435   return (read_history_range (filename, 0, -1));
 436 }
 437
 438 /* Read a range of lines from FILENAME, adding them to the history list.
 439    Start reading at the FROM'th line and end at the TO'th.  If FROM
 440    is zero, start at the beginning.  If TO is less than FROM, read
 441    until the end of the file.  If FILENAME is NULL, then read from
 442    ~/.history.  Returns 0 if successful, or errno if not. */
 443 int
 444 read_history_range (filename, from, to)
 445      char *filename;
 446      int from, to;
 447 {
 448   register int line_start, line_end;
 449   char *input, *buffer = (char *)NULL;
 450   int file, current_line;
 451   struct stat finfo;
 452   extern int errno;
 453
 454   input = history_filename (filename);
 455   file = open (input, O_RDONLY, 0666);
 456
 457   if ((file < 0) ||
 458       (stat (input, &finfo) == -1))
 459     goto error_and_exit;
 460
 461   buffer = (char *)xmalloc (finfo.st_size + 1);
 462
 463   if (read (file, buffer, finfo.st_size) != finfo.st_size)
 464   error_and_exit:
 465     {
 466       if (file >= 0)
 467         close (file);
 468
 469       if (buffer)
 470         free (buffer);
 471
 472       return (errno);
 473     }
 474
 475   close (file);
 476
 477   /* Set TO to larger than end of file if negative. */
 478   if (to < 0)
 479     to = finfo.st_size;
 480
 481   /* Start at beginning of file, work to end. */
 482   line_start = line_end = current_line = 0;
 483
 484   /* Skip lines until we are at FROM. */
 485   while (line_start < finfo.st_size && current_line < from)
 486     {
 487       for (line_end = line_start; line_end < finfo.st_size; line_end++)
 488         if (buffer[line_end] == '\n')
 489           {
 490             current_line++;
 491             line_start = line_end + 1;
 492             if (current_line == from)
 493               break;
 494           }
 495     }
 496
 497   /* If there are lines left to gobble, then gobble them now. */
 498   for (line_end = line_start; line_end < finfo.st_size; line_end++)
 499     if (buffer[line_end] == '\n')
 500       {
 501         buffer[line_end] = '\0';
 502
 503         if (buffer[line_start])
 504           add_history (buffer + line_start);
 505
 506         current_line++;
 507
 508         if (current_line >= to)
 509           break;
 510
 511         line_start = line_end + 1;
 512       }
 513   return (0);
 514 }
 515
 516 /* Truncate the history file FNAME, leaving only LINES trailing lines.
 517    If FNAME is NULL, then use ~/.history. */
 518 history_truncate_file (fname, lines)
 519      char *fname;
 520      register int lines;
 521 {
 522   register int i;
 523   int file;
 524   char *buffer = (char *)NULL, *filename;
 525   struct stat finfo;
 526
 527   filename = history_filename (fname);
 528   if (stat (filename, &finfo) == -1)
 529     goto truncate_exit;
 530
 531   file = open (filename, O_RDONLY, 0666);
 532
 533   if (file == -1)
 534     goto truncate_exit;
 535
 536   buffer = (char *)xmalloc (finfo.st_size + 1);
 537   read (file, buffer, finfo.st_size);
 538   close (file);
 539
 540   /* Count backwards from the end of buffer until we have passed
 541      LINES lines. */
 542   for (i = finfo.st_size; lines && i; i--)
 543     {
 544       if (buffer[i] == '\n')
 545         lines--;
 546     }
 547
 548   /* If there are fewer lines in the file than we want to truncate to,
 549      then we are all done. */
 550   if (!i)
 551     goto truncate_exit;
 552
 553   /* Otherwise, write from the start of this line until the end of the
 554      buffer. */
 555   for (--i; i; i--)
 556     if (buffer[i] == '\n')
 557       {
 558         i++;
 559         break;
 560       }
 561
 562   file = open (filename, O_WRONLY | O_TRUNC | O_CREAT, 0666);
 563   if (file == -1)
 564     goto truncate_exit;
 565
 566   write (file, buffer + i, finfo.st_size - i);
 567   close (file);
 568
 569  truncate_exit:
 570   if (buffer)
 571     free (buffer);
 572
 573   free (filename);
 574 }
 575
 576 #define HISTORY_APPEND 0
 577 #define HISTORY_OVERWRITE 1
 578
 579 /* Workhorse function for writing history.  Writes NELEMENT entries
 580    from the history list to FILENAME.  OVERWRITE is non-zero if you
 581    wish to replace FILENAME with the entries. */
 582 static int
 583 history_do_write (filename, nelements, overwrite)
 584      char *filename;
 585      int nelements, overwrite;
 586 {
 587   extern int errno;
 588   register int i, j;
 589   char *output = history_filename (filename);
 590   int file, mode;
 591
 592   if (overwrite)
 593     mode = O_WRONLY | O_CREAT | O_TRUNC;
 594   else
 595     mode = O_WRONLY | O_APPEND;
 596
 597   if ((file = open (output, mode, 0666)) == -1)
 598     return (errno);
 599
 600   if (nelements > history_length)
 601     nelements = history_length;
 602
 603   /* Build a buffer of all the lines to write, and write them in one syscall.
 604      Suggested by Peter Ho ([email protected]). */
 605   {
 606     register int j = 0;
 607     int buffer_size = 0;
 608     char *buffer;
 609
 610     /* Calculate the total number of bytes to write. */
 611     for (i = history_length - nelements; i < history_length; i++)
 612       buffer_size += 1 + strlen (the_history[i]->line);
 613
 614     /* Allocate the buffer, and fill it. */
 615     buffer = (char *)xmalloc (buffer_size);
 616
 617     for (i = history_length - nelements; i < history_length; i++)
 618       {
 619         strcpy (buffer + j, the_history[i]->line);
 620         j += strlen (the_history[i]->line);
 621         buffer[j++] = '\n';
 622       }
 623
 624     write (file, buffer, buffer_size);
 625     free (buffer);
 626   }
 627
 628   close (file);
 629   return (0);
 630 }
 631
 632 /* Append NELEMENT entries to FILENAME.  The entries appended are from
 633    the end of the list minus NELEMENTs up to the end of the list. */
 634 int
 635 append_history (nelements, filename)
 636      int nelements;
 637      char *filename;
 638 {
 639   return (history_do_write (filename, nelements, HISTORY_APPEND));
 640 }
 641
 642 /* Overwrite FILENAME with the current history.  If FILENAME is NULL,
 643    then write the history list to ~/.history.  Values returned
 644    are as in read_history ().*/
 645 int
 646 write_history (filename)
 647      char *filename;
 648 {
 649   return (history_do_write (filename, history_length, HISTORY_OVERWRITE));
 650 }
 651
 652 /* Return the history entry at the current position, as determined by
 653    history_offset.  If there is no entry there, return a NULL pointer. */
 654 HIST_ENTRY *
 655 current_history ()
 656 {
 657   if ((history_offset == history_length) || !the_history)
 658     return ((HIST_ENTRY *)NULL);
 659   else
 660     return (the_history[history_offset]);
 661 }
 662
 663 /* Back up history_offset to the previous history entry, and return
 664    a pointer to that entry.  If there is no previous entry then return
 665    a NULL pointer. */
 666 HIST_ENTRY *
 667 previous_history ()
 668 {
 669   if (!history_offset)
 670     return ((HIST_ENTRY *)NULL);
 671   else
 672     return (the_history[--history_offset]);
 673 }
 674
 675 /* Move history_offset forward to the next history entry, and return
 676    a pointer to that entry.  If there is no next entry then return a
 677    NULL pointer. */
 678 HIST_ENTRY *
 679 next_history ()
 680 {
 681   if (history_offset == history_length)
 682     return ((HIST_ENTRY *)NULL);
 683   else
 684     return (the_history[++history_offset]);
 685 }
 686
 687 /* Return the current history array.  The caller has to be carefull, since this
 688    is the actual array of data, and could be bashed or made corrupt easily.
 689    The array is terminated with a NULL pointer. */
 690 HIST_ENTRY **
 691 history_list ()
 692 {
 693   return (the_history);
 694 }
 695
 696 /* Return the history entry which is logically at OFFSET in the history array.
 697    OFFSET is relative to history_base. */
 698 HIST_ENTRY *
 699 history_get (offset)
 700      int offset;
 701 {
 702   int index = offset - history_base;
 703
 704   if (index >= history_length ||
 705       index < 0 ||
 706       !the_history)
 707     return ((HIST_ENTRY *)NULL);
 708   return (the_history[index]);
 709 }
 710
 711 /* Search for STRING in the history list.  DIR is < 0 for searching
 712    backwards.  POS is an absolute index into the history list at
 713    which point to begin searching. */
 714 int
 715 history_search_pos (string, dir, pos)
 716      char *string;
 717      int dir, pos;
 718 {
 719   int ret, old = where_history ();
 720   history_set_pos (pos);
 721   if (history_search (string, dir) == -1)
 722     {
 723       history_set_pos (old);
 724       return (-1);
 725     }
 726   ret = where_history ();
 727   history_set_pos (old);
 728   return ret;
 729 }
 730
 731 /* Make the current history item be the one at POS, an absolute index.
 732    Returns zero if POS is out of range, else non-zero. */
 733 int
 734 history_set_pos (pos)
 735      int pos;
 736 {
 737   if (pos > history_length || pos < 0 || !the_history)
 738     return (0);
 739   history_offset = pos;
 740   return (1);
 741 }
 742
 743 \f
 744 /* **************************************************************** */
 745 /*                                                                  */
 746 /*                      History Expansion                           */
 747 /*                                                                  */
 748 /* **************************************************************** */
 749
 750 /* Hairy history expansion on text, not tokens.  This is of general
 751    use, and thus belongs in this library. */
 752
 753 /* The last string searched for in a !?string? search. */
 754 static char *search_string = (char *)NULL;
 755
 756 /* Return the event specified at TEXT + OFFSET modifying OFFSET to
 757    point to after the event specifier.  Just a pointer to the history
 758    line is returned; NULL is returned in the event of a bad specifier.
 759    You pass STRING with *INDEX equal to the history_expansion_char that
 760    begins this specification.
 761    DELIMITING_QUOTE is a character that is allowed to end the string
 762    specification for what to search for in addition to the normal
 763    characters `:', ` ', `\t', `\n', and sometimes `?'.
 764    So you might call this function like:
 765    line = get_history_event ("!echo:p", &index, 0);  */
 766 char *
 767 get_history_event (string, caller_index, delimiting_quote)
 768      char *string;
 769      int *caller_index;
 770      int delimiting_quote;
 771 {
 772   register int i = *caller_index;
 773   int which, sign = 1;
 774   HIST_ENTRY *entry;
 775
 776   /* The event can be specified in a number of ways.
 777
 778      !!   the previous command
 779      !n   command line N
 780      !-n  current command-line minus N
 781      !str the most recent command starting with STR
 782      !?str[?]
 783           the most recent command containing STR
 784
 785      All values N are determined via HISTORY_BASE. */
 786
 787   if (string[i] != history_expansion_char)
 788     return ((char *)NULL);
 789
 790   /* Move on to the specification. */
 791   i++;
 792
 793   /* Handle !! case. */
 794   if (string[i] == history_expansion_char)
 795     {
 796       i++;
 797       which = history_base + (history_length - 1);
 798       *caller_index = i;
 799       goto get_which;
 800     }
 801
 802   /* Hack case of numeric line specification. */
 803  read_which:
 804   if (string[i] == '-')
 805     {
 806       sign = -1;
 807       i++;
 808     }
 809
 810   if (digit (string[i]))
 811     {
 812       int start = i;
 813
 814       /* Get the extent of the digits. */
 815       for (; digit (string[i]); i++);
 816
 817       /* Get the digit value. */
 818       sscanf (string + start, "%d", &which);
 819
 820       *caller_index = i;
 821
 822       if (sign < 0)
 823         which = (history_length + history_base) - which;
 824
 825     get_which:
 826       if (entry = history_get (which))
 827         return (entry->line);
 828
 829       return ((char *)NULL);
 830     }
 831
 832   /* This must be something to search for.  If the spec begins with
 833      a '?', then the string may be anywhere on the line.  Otherwise,
 834      the string must be found at the start of a line. */
 835   {
 836     int index;
 837     char *temp;
 838     int substring_okay = 0;
 839
 840     if (string[i] == '?')
 841       {
 842         substring_okay++;
 843         i++;
 844       }
 845
 846     for (index = i; string[i]; i++)
 847       if (whitespace (string[i]) ||
 848           string[i] == '\n' ||
 849           string[i] == ':' ||
 850           (substring_okay && string[i] == '?') ||
 851           string[i] == delimiting_quote)
 852         break;
 853
 854     temp = (char *)alloca (1 + (i - index));
 855     strncpy (temp, &string[index], (i - index));
 856     temp[i - index] = '\0';
 857
 858     if (string[i] == '?')
 859       i++;
 860
 861     *caller_index = i;
 862
 863   search_again:
 864
 865     index = history_search_internal
 866       (temp, -1, substring_okay ? NON_ANCHORED_SEARCH : ANCHORED_SEARCH);
 867
 868     if (index < 0)
 869     search_lost:
 870       {
 871         history_offset = history_length;
 872         return ((char *)NULL);
 873       }
 874
 875     if (index == 0)
 876       {
 877       search_won:
 878         entry = current_history ();
 879         history_offset = history_length;
 880
 881         /* If this was a substring search, then remember the string that
 882            we matched for word substitution. */
 883         if (substring_okay)
 884           {
 885             if (search_string)
 886               free (search_string);
 887             search_string = savestring (temp);
 888           }
 889
 890         return (entry->line);
 891       }
 892
 893     if (history_offset)
 894       history_offset--;
 895     else
 896       goto search_lost;
 897
 898     goto search_again;
 899   }
 900 }
 901
 902 /* Expand the string STRING, placing the result into OUTPUT, a pointer
 903    to a string.  Returns:
 904
 905    0) If no expansions took place (or, if the only change in
 906       the text was the de-slashifying of the history expansion
 907       character)
 908    1) If expansions did take place
 909   -1) If there was an error in expansion.
 910
 911   If an error ocurred in expansion, then OUTPUT contains a descriptive
 912   error message. */
 913 int
 914 history_expand (string, output)
 915      char *string;
 916      char **output;
 917 {
 918   register int j, l = strlen (string);
 919   int i, word_spec_error = 0;
 920   int cc, modified = 0;
 921   char *word_spec, *event;
 922   int starting_index, only_printing = 0, substitute_globally = 0;
 923
 924   char *get_history_word_specifier (), *rindex ();
 925
 926   /* The output string, and its length. */
 927   int len = 0;
 928   char *result = (char *)NULL;
 929
 930   /* Used in add_string; */
 931   char *temp, tt[2], tbl[3];
 932
 933   /* Prepare the buffer for printing error messages. */
 934   result = (char *)xmalloc (len = 255);
 935
 936   result[0] = tt[1] = tbl[2] = '\0';
 937   tbl[0] = '\\';
 938   tbl[1] = history_expansion_char;
 939
 940   /* Grovel the string.  Only backslash can quote the history escape
 941      character.  We also handle arg specifiers. */
 942
 943   /* Before we grovel forever, see if the history_expansion_char appears
 944      anywhere within the text. */
 945
 946   /* The quick substitution character is a history expansion all right.  That
 947      is to say, "^this^that^" is equivalent to "!!:s^this^that^", and in fact,
 948      that is the substitution that we do. */
 949   if (string[0] == history_subst_char)
 950     {
 951       char *format_string = (char *)alloca (10 + strlen (string));
 952
 953       sprintf (format_string, "%c%c:s%s",
 954                history_expansion_char, history_expansion_char,
 955                string);
 956       string = format_string;
 957       l += 4;
 958       goto grovel;
 959     }
 960
 961   /* If not quick substitution, still maybe have to do expansion. */
 962
 963   /* `!' followed by one of the characters in history_no_expand_chars
 964      is NOT an expansion. */
 965   for (i = 0; string[i]; i++)
 966     if (string[i] == history_expansion_char)
 967       if (!string[i + 1] || member (string[i + 1], history_no_expand_chars))
 968         continue;
 969       else
 970         goto grovel;
 971
 972   free (result);
 973   *output = savestring (string);
 974   return (0);
 975
 976  grovel:
 977
 978   for (i = j = 0; i < l; i++)
 979     {
 980       int tchar = string[i];
 981       if (tchar == history_expansion_char)
 982         tchar = -3;
 983
 984       switch (tchar)
 985         {
 986         case '\\':
 987           if (string[i + 1] == history_expansion_char)
 988             {
 989               i++;
 990               temp = tbl;
 991               goto do_add;
 992             }
 993           else
 994             goto add_char;
 995
 996           /* case history_expansion_char: */
 997         case -3:
 998           starting_index = i + 1;
 999           cc = string[i + 1];
1000
1001           /* If the history_expansion_char is followed by one of the
1002              characters in history_no_expand_chars, then it is not a
1003              candidate for expansion of any kind. */
1004           if (member (cc, history_no_expand_chars))
1005             goto add_char;
1006
1007           /* There is something that is listed as a `word specifier' in csh
1008              documentation which means `the expanded text to this point'.
1009              That is not a word specifier, it is an event specifier. */
1010
1011           if (cc == '#')
1012             goto hack_pound_sign;
1013
1014           /* If it is followed by something that starts a word specifier,
1015              then !! is implied as the event specifier. */
1016
1017           if (member (cc, ":$*%^"))
1018             {
1019               char fake_s[3];
1020               int fake_i = 0;
1021               i++;
1022               fake_s[0] = fake_s[1] = history_expansion_char;
1023               fake_s[2] = '\0';
1024               event = get_history_event (fake_s, &fake_i, 0);
1025             }
1026           else
1027             {
1028               int quoted_search_delimiter = 0;
1029
1030               /* If the character before this `!' is a double or single
1031                  quote, then this expansion takes place inside of the
1032                  quoted string.  If we have to search for some text ("!foo"),
1033                  allow the delimiter to end the search string. */
1034               if (i && (string[i - 1] == '\'' || string[i - 1] == '"'))
1035                 quoted_search_delimiter = string[i - 1];
1036
1037               event = get_history_event (string, &i, quoted_search_delimiter);
1038             }
1039
1040           if (!event)
1041           event_not_found:
1042             {
1043             int l = 1 + (i - starting_index);
1044
1045             temp = (char *)alloca (1 + l);
1046             strncpy (temp, string + starting_index, l);
1047             temp[l - 1] = 0;
1048             sprintf (result, "%s: %s.", temp,
1049                      word_spec_error ? "Bad word specifier" : "Event not found");
1050           error_exit:
1051             *output = result;
1052             return (-1);
1053           }
1054
1055           /* If a word specifier is found, then do what that requires. */
1056           starting_index = i;
1057
1058           word_spec = get_history_word_specifier (string, event, &i);
1059
1060           /* There is no such thing as a `malformed word specifier'.  However,
1061              it is possible for a specifier that has no match.  In that case,
1062              we complain. */
1063           if (word_spec == (char *)-1)
1064           bad_word_spec:
1065           {
1066             word_spec_error++;
1067             goto event_not_found;
1068           }
1069
1070           /* If no word specifier, than the thing of interest was the event. */
1071           if (!word_spec)
1072             temp = event;
1073           else
1074             {
1075               temp = (char *)alloca (1 + strlen (word_spec));
1076               strcpy (temp, word_spec);
1077               free (word_spec);
1078             }
1079
1080           /* Perhaps there are other modifiers involved.  Do what they say. */
1081
1082         hack_specials:
1083
1084           if (string[i] == ':')
1085             {
1086               char *tstr;
1087
1088               switch (string[i + 1])
1089                 {
1090                   /* :p means make this the last executed line.  So we
1091                      return an error state after adding this line to the
1092                      history. */
1093                 case 'p':
1094                   only_printing++;
1095                   goto next_special;
1096
1097                   /* :t discards all but the last part of the pathname. */
1098                 case 't':
1099                   tstr = rindex (temp, '/');
1100                   if (tstr)
1101                     temp = ++tstr;
1102                   goto next_special;
1103
1104                   /* :h discards the last part of a pathname. */
1105                 case 'h':
1106                   tstr = rindex (temp, '/');
1107                   if (tstr)
1108                     *tstr = '\0';
1109                   goto next_special;
1110
1111                   /* :r discards the suffix. */
1112                 case 'r':
1113                   tstr = rindex (temp, '.');
1114                   if (tstr)
1115                     *tstr = '\0';
1116                   goto next_special;
1117
1118                   /* :e discards everything but the suffix. */
1119                 case 'e':
1120                   tstr = rindex (temp, '.');
1121                   if (tstr)
1122                     temp = tstr;
1123                   goto next_special;
1124
1125                   /* :s/this/that substitutes `this' for `that'. */
1126                   /* :gs/this/that substitutes `this' for `that' globally. */
1127                 case 'g':
1128                   if (string[i + 2] == 's')
1129                     {
1130                       i++;
1131                       substitute_globally = 1;
1132                       goto substitute;
1133                     }
1134                   else
1135
1136                 case 's':
1137                   substitute:
1138                   {
1139                     char *this, *that, *new_event;
1140                     int delimiter = 0;
1141                     int si, l_this, l_that, l_temp = strlen (temp);
1142
1143                     if (i + 2 < strlen (string))
1144                       delimiter = string[i + 2];
1145
1146                     if (!delimiter)
1147                       break;
1148
1149                     i += 3;
1150
1151                     /* Get THIS. */
1152                     for (si = i; string[si] && string[si] != delimiter; si++);
1153                     l_this = (si - i);
1154                     this = (char *)alloca (1 + l_this);
1155                     strncpy (this, string + i, l_this);
1156                     this[l_this] = '\0';
1157
1158                     i = si;
1159                     if (string[si])
1160                       i++;
1161
1162                     /* Get THAT. */
1163                     for (si = i; string[si] && string[si] != delimiter; si++);
1164                     l_that = (si - i);
1165                     that = (char *)alloca (1 + l_that);
1166                     strncpy (that, string + i, l_that);
1167                     that[l_that] = '\0';
1168
1169                     i = si;
1170                     if (string[si]) i++;
1171
1172                     /* Ignore impossible cases. */
1173                     if (l_this > l_temp)
1174                       goto cant_substitute;
1175
1176                     /* Find the first occurrence of THIS in TEMP. */
1177                     si = 0;
1178                     for (; (si + l_this) <= l_temp; si++)
1179                       if (strncmp (temp + si, this, l_this) == 0)
1180                         {
1181                           new_event =
1182                             (char *)alloca (1 + (l_that - l_this) + l_temp);
1183                           strncpy (new_event, temp, si);
1184                           strncpy (new_event + si, that, l_that);
1185                           strncpy (new_event + si + l_that,
1186                                    temp + si + l_this,
1187                                    l_temp - (si + l_this));
1188                           new_event[(l_that - l_this) + l_temp] = '\0';
1189                           temp = new_event;
1190
1191                           if (substitute_globally)
1192                             {
1193                               si += l_that;
1194                               l_temp = strlen (temp);
1195                               substitute_globally++;
1196                               continue;
1197                             }
1198
1199                           goto hack_specials;
1200                         }
1201
1202                   cant_substitute:
1203
1204                     if (substitute_globally > 1)
1205                       {
1206                         substitute_globally = 0;
1207                         goto hack_specials;
1208                       }
1209
1210                     goto event_not_found;
1211                   }
1212
1213                   /* :# is the line so far.  Note that we have to
1214                      alloca () it since RESULT could be realloc ()'ed
1215                      below in add_string. */
1216                 case '#':
1217                 hack_pound_sign:
1218                   if (result)
1219                     {
1220                       temp = (char *)alloca (1 + strlen (result));
1221                       strcpy (temp, result);
1222                     }
1223                   else
1224                     temp = "";
1225
1226                 next_special:
1227                   i += 2;
1228                   goto hack_specials;
1229                 }
1230
1231             }
1232           /* Believe it or not, we have to back the pointer up by one. */
1233           --i;
1234           goto add_string;
1235
1236           /* A regular character.  Just add it to the output string. */
1237         default:
1238         add_char:
1239           tt[0] = string[i];
1240           temp = tt;
1241           goto do_add;
1242
1243         add_string:
1244           modified++;
1245
1246         do_add:
1247           j += strlen (temp);
1248           while (j > len)
1249             result = (char *)xrealloc (result, (len += 255));
1250
1251           strcpy (result + (j - strlen (temp)), temp);
1252         }
1253     }
1254
1255   *output = result;
1256
1257   if (only_printing)
1258     {
1259       add_history (result);
1260       return (-1);
1261     }
1262
1263   return (modified != 0);
1264 }
1265
1266 /* Return a consed string which is the word specified in SPEC, and found
1267    in FROM.  NULL is returned if there is no spec.  -1 is returned if
1268    the word specified cannot be found.  CALLER_INDEX is the offset in
1269    SPEC to start looking; it is updated to point to just after the last
1270    character parsed. */
1271 char *
1272 get_history_word_specifier (spec, from, caller_index)
1273      char *spec, *from;
1274      int *caller_index;
1275 {
1276   register int i = *caller_index;
1277   int first, last;
1278   int expecting_word_spec = 0;
1279   char *history_arg_extract ();
1280
1281   /* The range of words to return doesn't exist yet. */
1282   first = last = 0;
1283
1284   /* If we found a colon, then this *must* be a word specification.  If
1285      it isn't, then it is an error. */
1286   if (spec[i] == ':')
1287     i++, expecting_word_spec++;
1288
1289   /* Handle special cases first. */
1290
1291   /* `%' is the word last searched for. */
1292   if (spec[i] == '%')
1293     {
1294       *caller_index = i + 1;
1295       if (search_string)
1296         return (savestring (search_string));
1297       else
1298         return (savestring (""));
1299     }
1300
1301   /* `*' matches all of the arguments, but not the command. */
1302   if (spec[i] == '*')
1303     {
1304       char *star_result;
1305
1306       *caller_index = i + 1;
1307       star_result = history_arg_extract (1, '$', from);
1308
1309       if (!star_result)
1310         star_result = savestring ("");
1311
1312       return (star_result);
1313     }
1314
1315   /* `$' is last arg. */
1316   if (spec[i] == '$')
1317     {
1318       *caller_index = i + 1;
1319       return (history_arg_extract ('$', '$', from));
1320     }
1321
1322   /* Try to get FIRST and LAST figured out. */
1323   if (spec[i] == '-' || spec[i] == '^')
1324     {
1325       first = 1;
1326       goto get_last;
1327     }
1328
1329  get_first:
1330   if (digit (spec[i]) && expecting_word_spec)
1331     {
1332       sscanf (spec + i, "%d", &first);
1333       for (; digit (spec[i]); i++);
1334     }
1335   else
1336     return ((char *)NULL);
1337
1338  get_last:
1339   if (spec[i] == '^')
1340     {
1341       i++;
1342       last = 1;
1343       goto get_args;
1344     }
1345
1346   if (spec[i] != '-')
1347     {
1348       last = first;
1349       goto get_args;
1350     }
1351
1352   i++;
1353
1354   if (digit (spec[i]))
1355     {
1356       sscanf (spec + i, "%d", &last);
1357       for (; digit (spec[i]); i++);
1358     }
1359   else
1360     if (spec[i] == '$')
1361       {
1362         i++;
1363         last = '$';
1364       }
1365
1366  get_args:
1367   {
1368     char *result = (char *)NULL;
1369
1370     *caller_index = i;
1371
1372     if (last >= first)
1373       result = history_arg_extract (first, last, from);
1374
1375     if (result)
1376       return (result);
1377     else
1378       return ((char *)-1);
1379   }
1380 }
1381
1382 /* Extract the args specified, starting at FIRST, and ending at LAST.
1383    The args are taken from STRING.  If either FIRST or LAST is < 0,
1384    then make that arg count from the right (subtract from the number of
1385    tokens, so that FIRST = -1 means the next to last token on the line). */
1386 char *
1387 history_arg_extract (first, last, string)
1388      int first, last;
1389      char *string;
1390 {
1391   register int i, len;
1392   char *result = (char *)NULL;
1393   int size = 0, offset = 0;
1394
1395   char **history_tokenize (), **list;
1396
1397   if (!(list = history_tokenize (string)))
1398     return ((char *)NULL);
1399
1400   for (len = 0; list[len]; len++);
1401
1402   if (last < 0)
1403     last = len + last - 1;
1404
1405   if (first < 0)
1406     first = len + first - 1;
1407
1408   if (last == '$')
1409     last = len - 1;
1410
1411   if (first == '$')
1412     first = len - 1;
1413
1414   last++;
1415
1416   if (first > len || last > len || first < 0 || last < 0)
1417     result = ((char *)NULL);
1418   else
1419     {
1420       for (i = first; i < last; i++)
1421         {
1422           int l = strlen (list[i]);
1423
1424           if (!result)
1425             result = (char *)xmalloc ((size = (2 + l)));
1426           else
1427             result = (char *)xrealloc (result, (size += (2 + l)));
1428           strcpy (result + offset, list[i]);
1429           offset += l;
1430           if (i + 1 < last)
1431             {
1432               strcpy (result + offset, " ");
1433               offset++;
1434             }
1435         }
1436     }
1437
1438   for (i = 0; i < len; i++)
1439     free (list[i]);
1440
1441   free (list);
1442
1443   return (result);
1444 }
1445
1446 #define slashify_in_quotes "\\`\"$"
1447
1448 /* Return an array of tokens, much as the shell might.  The tokens are
1449    parsed out of STRING. */
1450 char **
1451 history_tokenize (string)
1452      char *string;
1453 {
1454   char **result = (char **)NULL;
1455   register int i, start, result_index, size;
1456   int len;
1457
1458   i = result_index = size = 0;
1459
1460   /* Get a token, and stuff it into RESULT.  The tokens are split
1461      exactly where the shell would split them. */
1462  get_token:
1463
1464   /* Skip leading whitespace. */
1465   for (; string[i] && whitespace(string[i]); i++);
1466
1467   start = i;
1468
1469   if (!string[i] || string[i] == history_comment_char)
1470     return (result);
1471
1472   if (member (string[i], "()\n")) {
1473     i++;
1474     goto got_token;
1475   }
1476
1477   if (member (string[i], "<>;&|")) {
1478     int peek = string[i + 1];
1479
1480     if (peek == string[i]) {
1481       if (peek ==  '<') {
1482         if (string[1 + 2] == '-')
1483           i++;
1484         i += 2;
1485         goto got_token;
1486       }
1487
1488       if (member (peek, ">:&|")) {
1489         i += 2;
1490         goto got_token;
1491       }
1492     } else {
1493       if ((peek == '&' &&
1494           (string[i] == '>' || string[i] == '<')) ||
1495           ((peek == '>') &&
1496           (string[i] == '&'))) {
1497         i += 2;
1498         goto got_token;
1499       }
1500     }
1501     i++;
1502     goto got_token;
1503   }
1504
1505   /* Get word from string + i; */
1506   {
1507     int delimiter = 0;
1508
1509     if (member (string[i], "\"'`"))
1510       delimiter = string[i++];
1511
1512     for (;string[i]; i++) {
1513
1514       if (string[i] == '\\') {
1515
1516         if (string[i + 1] == '\n') {
1517           i++;
1518           continue;
1519         } else {
1520           if (delimiter != '\'')
1521             if ((delimiter != '"') ||
1522                 (member (string[i], slashify_in_quotes))) {
1523               i++;
1524               continue;
1525             }
1526         }
1527       }
1528
1529       if (delimiter && string[i] == delimiter) {
1530         delimiter = 0;
1531         continue;
1532       }
1533
1534       if (!delimiter && (member (string[i], " \t\n;&()|<>")))
1535         goto got_token;
1536
1537       if (!delimiter && member (string[i], "\"'`")) {
1538         delimiter = string[i];
1539         continue;
1540       }
1541     }
1542     got_token:
1543
1544     len = i - start;
1545     if (result_index + 2 >= size) {
1546       if (!size)
1547         result = (char **)xmalloc ((size = 10) * (sizeof (char *)));
1548       else
1549         result =
1550           (char **)xrealloc (result, ((size += 10) * (sizeof (char *))));
1551     }
1552     result[result_index] = (char *)xmalloc (1 + len);
1553     strncpy (result[result_index], string + start, len);
1554     result[result_index][len] = '\0';
1555     result_index++;
1556     result[result_index] = (char *)NULL;
1557   }
1558   if (string[i])
1559     goto get_token;
1560
1561   return (result);
1562 }
1563
1564 #if defined (STATIC_MALLOC)
1565 \f
1566 /* **************************************************************** */
1567 /*                                                                  */
1568 /*                      xmalloc and xrealloc ()                     */
1569 /*                                                                  */
1570 /* **************************************************************** */
1571
1572 static void memory_error_and_abort ();
1573
1574 static char *
1575 xmalloc (bytes)
1576      int bytes;
1577 {
1578   char *temp = (char *)malloc (bytes);
1579
1580   if (!temp)
1581     memory_error_and_abort ();
1582   return (temp);
1583 }
1584
1585 static char *
1586 xrealloc (pointer, bytes)
1587      char *pointer;
1588      int bytes;
1589 {
1590   char *temp;
1591
1592   if (!pointer)
1593     temp = (char *)xmalloc (bytes);
1594   else
1595     temp = (char *)realloc (pointer, bytes);
1596
1597   if (!temp)
1598     memory_error_and_abort ();
1599
1600   return (temp);
1601 }
1602
1603 static void
1604 memory_error_and_abort ()
1605 {
1606   fprintf (stderr, "history: Out of virtual memory!\n");
1607   abort ();
1608 }
1609 #endif /* STATIC_MALLOC */
1610
1611 \f
1612 /* **************************************************************** */
1613 /*                                                                  */
1614 /*                              Test Code                           */
1615 /*                                                                  */
1616 /* **************************************************************** */
1617 #ifdef TEST
1618 main ()
1619 {
1620   char line[1024], *t;
1621   int done = 0;
1622
1623   line[0] = 0;
1624
1625   while (!done)
1626     {
1627       fprintf (stdout, "history%% ");
1628       t = gets (line);
1629
1630       if (!t)
1631         strcpy (line, "quit");
1632
1633       if (line[0])
1634         {
1635           char *expansion;
1636           int result;
1637
1638           using_history ();
1639
1640           result = history_expand (line, &expansion);
1641           strcpy (line, expansion);
1642           free (expansion);
1643           if (result)
1644             fprintf (stderr, "%s\n", line);
1645
1646           if (result < 0)
1647             continue;
1648
1649           add_history (line);
1650         }
1651
1652       if (strcmp (line, "quit") == 0) done = 1;
1653       if (strcmp (line, "save") == 0) write_history (0);
1654       if (strcmp (line, "read") == 0) read_history (0);
1655       if (strcmp (line, "list") == 0)
1656         {
1657           register HIST_ENTRY **the_list = history_list ();
1658           register int i;
1659
1660           if (the_list)
1661             for (i = 0; the_list[i]; i++)
1662               fprintf (stdout, "%d: %s\n", i + history_base, the_list[i]->line);
1663         }
1664       if (strncmp (line, "delete", strlen ("delete")) == 0)
1665         {
1666           int which;
1667           if ((sscanf (line + strlen ("delete"), "%d", &which)) == 1)
1668             {
1669               HIST_ENTRY *entry = remove_history (which);
1670               if (!entry)
1671                 fprintf (stderr, "No such entry %d\n", which);
1672               else
1673                 {
1674                   free (entry->line);
1675                   free (entry);
1676                 }
1677             }
1678           else
1679             {
1680               fprintf (stderr, "non-numeric arg given to `delete'\n");
1681             }
1682         }
1683     }
1684 }
1685
1686 #endif                          /* TEST */
1687 \f
1688 /*
1689 * Local variables:
1690 * compile-command: "gcc -g -DTEST -o history history.c"
1691 * end:
1692 */