readline/history.c

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