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