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