home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 113 / EnigmaAmiga113CD.iso / software / sviluppo / sed-3.02 / sed / execute.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-06  |  30.1 KB  |  1,232 lines
  1. /*  GNU SED, a batch stream editor.
  2.     Copyright (C) 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1998
  3.     Free Software Foundation, Inc.
  4.  
  5.     This program is free software; you can redistribute it and/or modify
  6.     it under the terms of the GNU General Public License as published by
  7.     the Free Software Foundation; either version 2, or (at your option)
  8.     any later version.
  9.  
  10.     This program is distributed in the hope that it will be useful,
  11.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.     GNU General Public License for more details.
  14.  
  15.     You should have received a copy of the GNU General Public License
  16.     along with this program; if not, write to the Free Software
  17.     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  18.  
  19. #undef EXPERIMENTAL_DASH_N_OPTIMIZATION    /*don't use -- is buggy*/
  20. #define INITIAL_BUFFER_SIZE    50
  21. #define LCMD_OUT_LINE_LEN    70
  22. #define FREAD_BUFFER_SIZE    8192
  23.  
  24. #include "config.h"
  25. #include <stdio.h>
  26. #include <ctype.h>
  27.  
  28. #include <errno.h>
  29. #ifndef errno
  30. extern int errno;
  31. #endif
  32.  
  33. #ifdef HAVE_ISATTY
  34. # ifdef HAVE_UNISTD_H
  35. #  include <unistd.h>
  36. # endif
  37. #endif
  38.  
  39. #ifdef __GNUC__
  40. # if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__-0 >= 7)
  41.   /* silence warning about unused parameter even for "gcc -W -Wunused" */
  42. #  define UNUSED    __attribute__((unused))
  43. # endif
  44. #endif
  45. #ifndef UNUSED
  46. # define UNUSED
  47. #endif
  48.  
  49. #ifndef HAVE_STRING_H
  50. # include <strings.h>
  51. # ifdef HAVE_MEMORY_H
  52. #  include <memory.h>
  53. # endif
  54. #else
  55. # include <string.h>
  56. #endif /* HAVE_STRING_H */
  57.  
  58. #ifdef HAVE_STDLIB_H
  59. # include <stdlib.h>
  60. #endif
  61.  
  62. #ifdef HAVE_SYS_TYPES_H
  63. # include <sys/types.h>
  64. #endif
  65. #include "regex-sed.h"
  66. #include "basicdefs.h"
  67. #include "utils.h"
  68. #include "sed.h"
  69.  
  70. #ifdef BOOTSTRAP
  71. # ifdef memchr
  72. #  undef memchr
  73. # endif
  74. # define memchr bootstrap_memchr
  75. static VOID *bootstrap_memchr P_((const VOID *s, int c, size_t n));
  76. #endif /*BOOTSTRAP*/
  77.  
  78. #ifndef HAVE_REGNEXEC
  79. # define regnexec(x,t,l,r,n,f)    regexec(x,t,r,n,f)
  80. #endif
  81.  
  82. /* If set, don't write out the line unless explicitly told to */
  83. extern flagT no_default_output;
  84.  
  85. /* Do we need to be pedantically POSIX compliant? */
  86. extern flagT POSIXLY_CORRECT;
  87.  
  88.  
  89. /* Sed operates a line at a time. */
  90. struct line {
  91.   char *text;        /* Pointer to line allocated by malloc. */
  92.   char *active;        /* Pointer to non-consumed part of text. */
  93.   size_t length;    /* Length of text (or active, if used). */
  94.   size_t alloc;        /* Allocated space for text. */
  95.   flagT chomped;    /* Was a trailing newline dropped? */
  96. };
  97.  
  98. /* A queue of text to write out at the end of a cycle
  99.    (filled by the "a" and "r" commands.) */
  100. struct append_queue {
  101.   const char *rfile;
  102.   const char *text;
  103.   size_t textlen;
  104.   struct append_queue *next;
  105. };
  106.  
  107. /* State information for the input stream. */
  108. struct input {
  109.   char **file_list;    /* The list of yet-to-be-opened files.
  110.                It is invalid for file_list to be NULL.
  111.                When *file_list is NULL we are
  112.                currently processing the last file. */
  113.   countT bad_count;    /* count of files we failed to open */
  114.   countT line_number;    /* Current input line number (over all files) */
  115.  
  116.   flagT (*read_fn) P_((struct input *));    /* read one line */
  117.   /* If fp is NULL, read_fn better not be one which uses fp;
  118.      in particular, read_always_fail() is recommended. */
  119.  
  120.   FILE *fp;        /* if NULL, none of the following are valid */
  121.   VOID *base;        /* if non-NULL, we are using mmap()ed input */
  122.   const char *cur;    /* only valid if base is non-NULL */
  123.   size_t length;    /* only valid if base is non-NULL */
  124.   size_t left;        /* only valid if base is non-NULL */
  125. #ifdef HAVE_ISATTY
  126.   flagT is_tty;        /* only valid if base is NULL */
  127. #endif
  128. };
  129.  
  130. static void resize_line P_((struct line *lb, size_t len));
  131. static void open_next_file P_((const char *name, struct input *input));
  132. static void closedown P_((struct input *input));
  133. static flagT read_always_fail P_((struct input *input));
  134. static flagT read_mem_line P_((struct input *input));
  135. static size_t slow_getline P_((char *buf, size_t buflen, FILE *in));
  136. static flagT read_file_line P_((struct input *input));
  137. static flagT read_pattern_space P_((struct input *input, flagT append));
  138. static flagT last_file_with_data_p P_((struct input *input));
  139. static flagT test_dollar_EOF P_((struct input *input));
  140. static flagT match_an_address_p P_((struct addr *, struct input *, flagT));
  141. static flagT match_address_p P_((struct sed_cmd *cmd, struct input *input));
  142. static void do_list P_((void));
  143. static void do_subst P_((struct subst *subst));
  144. static flagT execute_program P_((struct vector *, struct input *input));
  145. static void output_line
  146.         P_((const char *text, size_t length, flagT nl, FILE *fp));
  147. static void line_init P_((struct line *buf, size_t initial_size));
  148. static void line_copy P_((struct line *from, struct line *to));
  149. static void str_append P_((struct line *to, const char *string, size_t length));
  150. static void nul_append P_((struct line *dest));
  151. static void line_append P_((struct line *from, struct line *to));
  152. static void dump_append_queue P_((void));
  153. static struct append_queue *next_append_slot P_((void));
  154.  
  155. #ifdef EXPERIMENTAL_DASH_N_OPTIMIZATION
  156. static countT count_branches P_((struct vector *));
  157. static struct sed_cmd *shrink_program
  158.         P_((struct vector *vec, struct sed_cmd *cur_cmd, countT*n));
  159.  
  160. /* Used to attempt a simple-minded optimization. */
  161. static countT branches_in_top_level;
  162. #endif /*EXPERIMENTAL_DASH_N_OPTIMIZATION*/
  163.  
  164.  
  165. /* Have we done any replacements lately?  This is used by the 't' command. */
  166. static flagT replaced = 0;
  167.  
  168. /* The 'current' input line. */
  169. static struct line line;
  170.  
  171. /* An input line that's been stored by later use by the program */
  172. static struct line hold;
  173.  
  174. /* The buffered input look-ahead. */
  175. static struct line buffer;
  176.  
  177. static struct append_queue *append_head = NULL;
  178. static struct append_queue *append_tail = NULL;
  179.  
  180.  
  181. /* Apply the compiled script to all the named files. */
  182. countT
  183. process_files(the_program, argv)
  184.   struct vector *the_program;
  185.   char **argv;
  186. {
  187.   static char dash[] = "-";
  188.   static char *stdin_argv[2] = { dash, NULL };
  189.   struct input input;
  190.  
  191. #ifdef EXPERIMENTAL_DASH_N_OPTIMIZATION
  192.   branches_in_top_level = count_branches(the_program);
  193. #endif /*EXPERIMENTAL_DASH_N_OPTIMIZATION*/
  194.   input.file_list = stdin_argv;
  195.   if (argv && *argv)
  196.     input.file_list = argv;
  197.   input.bad_count = 0;
  198.   input.line_number = 0;
  199.   input.read_fn = read_always_fail;
  200.   input.fp = NULL;
  201.  
  202.   line_init(&line, INITIAL_BUFFER_SIZE);
  203.   line_init(&hold, INITIAL_BUFFER_SIZE);
  204.   line_init(&buffer, FREAD_BUFFER_SIZE);
  205.  
  206.   while (read_pattern_space(&input, 0))
  207.     {
  208.       flagT quit = execute_program(the_program, &input);
  209.       if (!no_default_output)
  210.     output_line(line.text, line.length, line.chomped, stdout);
  211.       if (quit)
  212.     break;
  213.     }
  214.   closedown(&input);
  215.   return input.bad_count;
  216. }
  217.  
  218. /* increase a struct line's length, making some attempt at
  219.    keeping realloc() calls under control by padding for future growth.  */
  220. static void
  221. resize_line(lb, len)
  222.   struct line *lb;
  223.   size_t len;
  224. {
  225.   lb->alloc *= 2;
  226.   if (lb->alloc - lb->length < len)
  227.     lb->alloc = lb->length + len;
  228.   lb->text = REALLOC(lb->text, lb->alloc, char);
  229. }
  230.  
  231. /* Initialize a struct input for the named file. */
  232. static void
  233. open_next_file(name, input)
  234.   const char *name;
  235.   struct input *input;
  236. {
  237.   input->base = NULL;
  238.   buffer.length = 0;
  239.  
  240.   if (name[0] == '-' && name[1] == '\0')
  241.     {
  242.       clearerr(stdin);    /* clear any stale EOF indication */
  243.       input->fp = stdin;
  244.     }
  245.   else if ( ! (input->fp = fopen(name, "r")) )
  246.     {
  247.       const char *ptr = strerror(errno);
  248.       fprintf(stderr, "%s: can't read %s: %s\n", myname, name, ptr);
  249.       input->read_fn = read_always_fail; /* a redundancy */
  250.       ++input->bad_count;
  251.       return;
  252.     }
  253.  
  254.   input->read_fn = read_file_line;
  255.   if (map_file(input->fp, &input->base, &input->length))
  256.     {
  257.       input->cur = VCAST(char *)input->base;
  258.       input->left = input->length;
  259.       input->read_fn = read_mem_line;
  260.     }
  261. #ifdef HAVE_ISATTY
  262.   else
  263.     input->is_tty = isatty(fileno(input->fp));
  264. #endif
  265. }
  266.  
  267. /* Clean up an input stream that we are done with. */
  268. static void
  269. closedown(input)
  270.   struct input *input;
  271. {
  272.   input->read_fn = read_always_fail;
  273.   if (!input->fp)
  274.     return;
  275.   if (input->base)
  276.     unmap_file(input->base, input->length);
  277.   if (input->fp != stdin) /* stdin can be reused on tty and tape devices */
  278.     ck_fclose(input->fp);
  279.   input->fp = NULL;
  280. }
  281.  
  282. /* dummy function to simplify read_pattern_space() */
  283. static flagT
  284. read_always_fail(input)
  285.   struct input *input UNUSED;
  286. {
  287.   return 0;
  288. }
  289.  
  290. /* The quick-and-easy mmap()'d case... */
  291. static flagT
  292. read_mem_line(input)
  293.   struct input *input;
  294. {
  295.   const char *e;
  296.   size_t l;
  297.  
  298.   if ( (e = memchr(input->cur, '\n', input->left)) )
  299.     {
  300.       /* common case */
  301.       l = e++ - input->cur;
  302.       line.chomped = 1;
  303.     }
  304.   else
  305.     {
  306.       /* This test is placed _after_ the memchr() fails for performance
  307.      reasons (because this branch is the uncommon case and the
  308.      memchr() will safely fail if input->left == 0).  Okay, so the
  309.      savings is trivial.  I'm doing it anyway. */
  310.       if (input->left == 0)
  311.     return 0;
  312.       e = input->cur + input->left;
  313.       l = input->left;
  314.       if (*input->file_list || POSIXLY_CORRECT)
  315.     line.chomped = 1;
  316.     }
  317.  
  318.   if (line.alloc - line.length < l)
  319.     resize_line(&line, l);
  320.   memcpy(line.text + line.length, input->cur, l);
  321.   line.length += l;
  322.   input->left -= e - input->cur;
  323.   input->cur = e;
  324.   return 1;
  325. }
  326.  
  327. #ifdef HAVE_ISATTY
  328. /* fgets() doesn't let us handle NULs and fread() buffers too much
  329.  * for interactive use.
  330.  */
  331. static size_t
  332. slow_getline(buf, buflen, in)
  333.   char *buf;
  334.   size_t buflen;
  335.   FILE *in;
  336. {
  337.   size_t resultlen = 0;
  338.   int c;
  339.  
  340.   while (resultlen<buflen && (c=getc(in))!=EOF)
  341.     {
  342.       ++resultlen;
  343.       *buf++ = c;
  344.       if (c == '\n')
  345.     break;
  346.     }
  347.   if (ferror(in))
  348.     panic("input read error: %s", strerror(errno));
  349.   return resultlen;
  350. }
  351. #endif /*HAVE_ISATTY*/
  352.  
  353. static flagT
  354. read_file_line(input)
  355.   struct input *input;
  356. {
  357.   char *b;
  358.   size_t blen;
  359.   size_t initial_length = line.length;
  360.  
  361.   if (!buffer.active)
  362.     buffer.active = buffer.text;
  363.   while (!(b = memchr(buffer.active, '\n', buffer.length)))
  364.     {
  365.       if (line.alloc-line.length < buffer.length)
  366.     resize_line(&line, buffer.length);
  367.       memcpy(line.text+line.length, buffer.active, buffer.length);
  368.       line.length += buffer.length;
  369.       buffer.length = 0;
  370.       if (!feof(input->fp))
  371.     {
  372. #ifdef HAVE_ISATTY
  373.       if (input->is_tty)
  374.         buffer.length = slow_getline(buffer.text, buffer.alloc, input->fp);
  375.       else
  376. #endif
  377.         buffer.length = ck_fread(buffer.text, 1, buffer.alloc, input->fp);
  378.     }
  379.  
  380.       if (buffer.length == 0)
  381.     {
  382.       if (*input->file_list || POSIXLY_CORRECT)
  383.         line.chomped = 1;
  384.       /* Did we hit EOF without reading anything?  If so, try
  385.          the next file; otherwise just go with what we did get. */
  386.       return (line.length > initial_length);
  387.     }
  388.       buffer.active = buffer.text;
  389.     }
  390.  
  391.   blen = b - buffer.active;
  392.   if (line.alloc-line.length < blen)
  393.     resize_line(&line, blen);
  394.   memcpy(line.text+line.length, buffer.active, blen);
  395.   line.length += blen;
  396.   ++blen;
  397.   line.chomped = 1;
  398.   buffer.active += blen;
  399.   buffer.length -= blen;
  400.   return 1;
  401. }
  402.  
  403. /* Read in the next line of input, and store it in the pattern space.
  404.    Return zero if there is nothing left to input. */
  405. static flagT
  406. read_pattern_space(input, append)
  407.   struct input *input;
  408.   flagT append;
  409. {
  410.   dump_append_queue();
  411.   replaced = 0;
  412.   line.chomped = 0;
  413.   if (!append)
  414.     line.length = 0;
  415.  
  416.   while ( ! (*input->read_fn)(input) )
  417.     {
  418.       closedown(input);
  419.       if (!*input->file_list)
  420.     return 0;
  421.       open_next_file(*input->file_list++, input);
  422.     }
  423.  
  424.   ++input->line_number;
  425.   return 1;
  426. }
  427.  
  428. static flagT
  429. last_file_with_data_p(input)
  430.   struct input *input;
  431. {
  432.   /*XXX reference implementation is equivalent to:
  433.       return !*input->file_list;
  434.    */
  435.   for (;;)
  436.     {
  437.       int ch;
  438.  
  439.       closedown(input);
  440.       if (!*input->file_list)
  441.     return 1;
  442.       open_next_file(*input->file_list++, input);
  443.       if (input->fp)
  444.     {
  445.       if (input->base)
  446.         {
  447.           if (0 < input->left)
  448.         return 0;
  449.         }
  450.       else if ((ch = getc(input->fp)) != EOF)
  451.         {
  452.           ungetc(ch, input->fp);
  453.           return 0;
  454.         }
  455.     }
  456.     }
  457. }
  458.  
  459. /* Determine if we match the '$' address.  */
  460. static flagT
  461. test_dollar_EOF(input)
  462.   struct input *input;
  463. {
  464.   int ch;
  465.  
  466.   if (buffer.length)
  467.     return 0;
  468.   if (!input->fp)
  469.     return last_file_with_data_p(input);
  470.   if (input->base)
  471.     return (input->left==0 && last_file_with_data_p(input));
  472.   if (feof(input->fp))
  473.     return last_file_with_data_p(input);
  474.   if ((ch = getc(input->fp)) == EOF)
  475.     return last_file_with_data_p(input);
  476.   ungetc(ch, input->fp);
  477.   return 0;
  478. }
  479.  
  480. /* Append a NUL char after the end of DEST, without resizing DEST.
  481.    This is to permit the use of regexp routines which expect C strings
  482.    instead of counted strings.
  483.  */
  484. static void
  485. nul_append(dest)
  486.   struct line *dest;
  487. {
  488. #ifndef HAVE_REGNEXEC
  489.   if (dest->alloc - dest->length < 1)
  490.     resize_line(dest, 1);
  491.   dest->text[dest->length] = '\0';
  492. #endif
  493. }
  494.  
  495. /* Return non-zero if the current line matches the address
  496.    pointed to by 'addr'.  */
  497. static flagT
  498. match_an_address_p(addr, input, is_addr2_p)
  499.   struct addr *addr;
  500.   struct input *input;
  501.   flagT is_addr2_p;
  502. {
  503.   switch (addr->addr_type)
  504.     {
  505.     case addr_is_null:
  506.       return 1;
  507.     case addr_is_num:
  508.       if (is_addr2_p)
  509.     return (input->line_number >= addr->a.addr_number);
  510.       return (input->line_number == addr->a.addr_number);
  511.     case addr_is_mod:
  512.       if (addr->a.m.offset < addr->a.m.modulo)
  513.     return (input->line_number%addr->a.m.modulo == addr->a.m.offset);
  514.       /* offset >= modulo implies we have an extra initial skip */
  515.       if (input->line_number < addr->a.m.offset)
  516.     return 0;
  517.       /* normalize */
  518.       addr->a.m.offset %= addr->a.m.modulo;
  519.       return 1;
  520.     case addr_is_last:
  521.       return test_dollar_EOF(input);
  522.     case addr_is_regex:
  523.       nul_append(&line);
  524.       return !regnexec(addr->a.addr_regex,
  525.             line.text, line.length, 0, NULL, 0);
  526.     default:
  527.       panic("INTERNAL ERROR: bad address type");
  528.     }
  529.   /*NOTREACHED*/
  530.   return 0;
  531. }
  532.  
  533. /* return non-zero if current address is valid for cmd */
  534. static flagT
  535. match_address_p(cmd, input)
  536.   struct sed_cmd *cmd;
  537.   struct input *input;
  538. {
  539.   flagT addr_matched = cmd->a1_matched;
  540.  
  541.   if (addr_matched)
  542.     {
  543.       if (match_an_address_p(&cmd->a2, input, 1))
  544.     cmd->a1_matched = 0;
  545.     }
  546.   else if (match_an_address_p(&cmd->a1, input, 0))
  547.     {
  548.       addr_matched = 1;
  549.       if (cmd->a2.addr_type != addr_is_null)
  550.     if (   (cmd->a2.addr_type == addr_is_regex)
  551.         || !match_an_address_p(&cmd->a2, input, 1))
  552.       cmd->a1_matched = 1;
  553.     }
  554.   if (cmd->addr_bang)
  555.     addr_matched = !addr_matched;
  556.   return addr_matched;
  557. }
  558.  
  559. static void
  560. do_list()
  561. {
  562.   unsigned char *p = CAST(unsigned char *)line.text;
  563.   countT len = line.length;
  564.   countT width = 0;
  565.   char obuf[180];    /* just in case we encounter a 512-bit char ;-) */
  566.   char *o;
  567.   size_t olen;
  568.  
  569.   for (; len--; ++p) {
  570.       o = obuf;
  571.       if (ISPRINT(*p)) {
  572.       *o++ = *p;
  573.       if (*p == '\\')
  574.         *o++ = '\\';
  575.       } else {
  576.       *o++ = '\\';
  577.       switch (*p) {
  578. #if defined __STDC__ && __STDC__
  579.         case '\a': *o++ = 'a'; break;
  580. #else
  581.         /* If not STDC we'll just assume ASCII */
  582.         case 007:  *o++ = 'a'; break;
  583. #endif
  584.         case '\b': *o++ = 'b'; break;
  585.         case '\f': *o++ = 'f'; break;
  586.         case '\n': *o++ = 'n'; break;
  587.         case '\r': *o++ = 'r'; break;
  588.         case '\t': *o++ = 't'; break;
  589.         case '\v': *o++ = 'v'; break;
  590.         default:
  591.           sprintf(o, "%03o", *p);
  592.           o += strlen(o);
  593.           break;
  594.         }
  595.       }
  596.       olen = o - obuf;
  597.       if (width+olen >= LCMD_OUT_LINE_LEN) {
  598.       ck_fwrite("\\\n", 1, 2, stdout);
  599.       width = 0;
  600.       }
  601.       ck_fwrite(obuf, 1, olen, stdout);
  602.       width += olen;
  603.   }
  604.   ck_fwrite("$\n", 1, 2, stdout);
  605. }
  606.  
  607. static void
  608. do_subst(sub)
  609.   struct subst *sub;
  610. {
  611.   /* s_accum will accumulate the result of the s command. */
  612.   /* static so as to keep malloc() calls down */
  613.   static struct line s_accum;
  614.  
  615.   size_t start;        /* where to start scan for match in LINE */
  616.   size_t offset;    /* where in LINE a match was found */
  617.   size_t remain;    /* length after START, sans trailing newline */
  618.   countT count;        /* number of matches found */
  619.   char *rep;        /* the replacement string */
  620.   char *rep_end;    /* end of the replacement string */
  621.   flagT not_bol_p;
  622.   flagT did_subst;
  623.   regmatch_t regs[10];
  624.  
  625.   if (s_accum.alloc == 0)
  626.     line_init(&s_accum, INITIAL_BUFFER_SIZE);
  627.   s_accum.length = 0;
  628.  
  629.   count = 0;
  630.   did_subst = 0;
  631.   not_bol_p = 0;
  632.   start = 0;
  633.   remain = line.length - start;
  634.   rep = sub->replacement;
  635.   rep_end = rep + sub->replace_length;
  636.  
  637.   nul_append(&line);
  638.   while ( ! regnexec(sub->regx,
  639.              line.text + start, remain,
  640.              sizeof(regs) / sizeof(regs[0]), regs, not_bol_p) )
  641.     {
  642.       ++count;
  643.       offset = regs[0].rm_so + start;
  644.  
  645.       /*
  646.        *  +- line.text   +-[offset]
  647.        *  V              V
  648.        * "blah blah blah xyzzy blah blah blah blah"
  649.        *       ^             ^                    ^
  650.        *       +-[start]     +-[end]              +-[start + remain]
  651.        *
  652.        *
  653.        * regs[0].rm_so == offset - start
  654.        * regs[0].rm_eo == end - start
  655.        */
  656.  
  657.       /* Copy stuff to the left of the next match into the output
  658.        * string.
  659.        */
  660.       if (start < offset)
  661.     str_append(&s_accum, line.text + start, offset - start);
  662.  
  663.       /* If we're counting up to the Nth match, are we there yet? */
  664.       if (count < sub->numb)
  665.     {
  666.       /* Not there yet...so skip this match. */
  667.       size_t matched = regs[0].rm_eo - regs[0].rm_so;
  668.  
  669.       /* If the match was vacuous, skip ahead one character
  670.        * anyway.   It isn't at all obvious to me that this is
  671.        * the right behavior for this case.    -t    XXX
  672.        */
  673.       if (matched == 0 && offset < line.length)
  674.         matched = 1;
  675.       str_append(&s_accum, line.text + offset, matched);
  676.       start = offset + matched;
  677.       remain = line.length - start;
  678.       not_bol_p = 1;
  679.       continue;
  680.     }
  681.  
  682.       /* Expand the replacement string into the output string. */
  683.       {
  684.     char *rep_cur;    /* next burst being processed in replacement */
  685.     char *rep_next;    /* end of burst in replacement */
  686.  
  687.     /* Replacement strings can be viewed as a sequence of variable
  688.      * length commands.  A command can be a literal string or a
  689.      * backreference (either numeric or "&").
  690.      *
  691.      * This loop measures off the next command between
  692.      * REP_CUR and REP_NEXT, handles that command, and loops.
  693.      */
  694.     for (rep_next = rep_cur = rep;
  695.          rep_next < rep_end;
  696.          rep_next++)
  697.       {
  698.         if (*rep_next == '\\')
  699.           {
  700.         /* Preceding the backslash may be some literal
  701.          * text:
  702.          */
  703.         if (rep_cur < rep_next)
  704.           str_append(&s_accum, rep_cur,
  705.                  CAST(size_t)(rep_next - rep_cur));
  706.  
  707.         /* Skip the backslash itself and look for
  708.          * a numeric back-reference:
  709.          */
  710.         rep_next++;
  711.         if (rep_next < rep_end
  712.             && '0' <= *rep_next && *rep_next <= '9')
  713.           {
  714.             int i = *rep_next - '0';
  715.             str_append(&s_accum, line.text + start + regs[i].rm_so,
  716.                    CAST(size_t)(regs[i].rm_eo-regs[i].rm_so));
  717.           }
  718.         else
  719.           str_append(&s_accum, rep_next, 1);
  720.         rep_cur = rep_next + 1;
  721.           }
  722.         else if (*rep_next == '&')
  723.           {
  724.         /* Preceding the ampersand may be some literal
  725.          * text:
  726.          */
  727.         if (rep_cur < rep_next)
  728.           str_append(&s_accum, rep_cur,
  729.                  CAST(size_t)(rep_next - rep_cur));
  730.         str_append(&s_accum, line.text + start + regs[0].rm_so,
  731.                CAST(size_t)(regs[0].rm_eo - regs[0].rm_so));
  732.         rep_cur = rep_next + 1;
  733.           }
  734.       }
  735.  
  736.     /* There may be a trailing literal in the replacement string. */
  737.     if (rep_cur < rep_next)
  738.       str_append(&s_accum, rep_cur, CAST(size_t)(rep_next - rep_cur));
  739.       }
  740.  
  741.       did_subst = 1;
  742.       not_bol_p = 1;
  743.       start += regs[0].rm_eo;
  744.       remain = line.length - start;
  745.       if (!sub->global || remain == 0)
  746.     break;
  747.  
  748.       /* If the match was vacuous, skip over one character
  749.        * and add that character to the output.
  750.        */
  751.       if (regs[0].rm_so == regs[0].rm_eo)
  752.     {
  753.       str_append(&s_accum, line.text + offset, 1);
  754.       ++start;
  755.       --remain;
  756.     }
  757.     }
  758.  
  759.   if (did_subst)
  760.     {
  761.       struct line tmp;
  762.       if (start < line.length)
  763.     str_append(&s_accum, line.text + start, remain);
  764.       memcpy(VCAST(VOID *)&tmp, VCAST(VOID *)&line, sizeof line);
  765.       memcpy(VCAST(VOID *)&line, VCAST(VOID *)&s_accum, sizeof line);
  766.       line.chomped = tmp.chomped;
  767.       memcpy(VCAST(VOID *)&s_accum, VCAST(VOID *)&tmp, sizeof line);
  768.       if (sub->wfile)
  769.     output_line(line.text, line.length, line.chomped, sub->wfile);
  770.       if (sub->print)
  771.     output_line(line.text, line.length, line.chomped, stdout);
  772.       replaced = 1;
  773.     }
  774. }
  775.  
  776. /* Execute the program 'vec' on the current input line.
  777.    Return non-zero if caller should quit, 0 otherwise.  */
  778. static flagT
  779. execute_program(vec, input)
  780.   struct vector *vec;
  781.   struct input *input;
  782. {
  783.   struct vector *cur_vec;
  784.   struct sed_cmd *cur_cmd;
  785.   size_t n;
  786.  
  787.   cur_vec = vec;
  788.   cur_cmd = cur_vec->v;
  789.   n = cur_vec->v_length;
  790.   while (n)
  791.     {
  792.       if (match_address_p(cur_cmd, input))
  793.     {
  794.       switch (cur_cmd->cmd)
  795.         {
  796.         case '{':        /* Execute sub-program */
  797.           if (cur_cmd->x.sub->v_length)
  798.         {
  799.           cur_vec = cur_cmd->x.sub;
  800.           cur_cmd = cur_vec->v;
  801.           n = cur_vec->v_length;
  802.           continue;
  803.         }
  804.           break;
  805.  
  806.         case '}':
  807.           {
  808.         countT i = cur_vec->return_i;
  809.         cur_vec = cur_vec->return_v;
  810.         cur_cmd = cur_vec->v + i;
  811.         n = cur_vec->v_length - i;
  812.           }
  813.           continue;
  814.  
  815.         case 'a':
  816.           {
  817.         struct append_queue *aq = next_append_slot();
  818.         aq->text = cur_cmd->x.cmd_txt.text;
  819.         aq->textlen = cur_cmd->x.cmd_txt.text_len;
  820.           }
  821.           break;
  822.  
  823.         case 'b':
  824.           if (cur_cmd->x.jump)
  825.         {
  826.           struct sed_label *j = cur_cmd->x.jump;
  827.           countT i = j->v_index;
  828.           cur_vec = j->v;
  829.           cur_cmd = cur_vec->v + i;
  830.           n = cur_vec->v_length - i;
  831.           continue;
  832.         }
  833.           return 0;
  834.  
  835.         case 'c':
  836.           line.length = 0;
  837.           line.chomped = 0;
  838.           if (!cur_cmd->a1_matched)
  839.         output_line(cur_cmd->x.cmd_txt.text,
  840.                 cur_cmd->x.cmd_txt.text_len, 0, stdout);
  841.           /* POSIX.2 is silent about c starting a new cycle,
  842.          but it seems to be expected (and make sense). */
  843.           return 0;
  844.  
  845.         case 'd':
  846.           line.length = 0;
  847.           line.chomped = 0;
  848.           return 0;
  849.  
  850.         case 'D':
  851.           {
  852.         char *p = memchr(line.text, '\n', line.length);
  853.         if (!p)
  854.           {
  855.             line.length = 0;
  856.             line.chomped = 0;
  857.             return 0;
  858.           }
  859.         ++p;
  860.         memmove(line.text, p, line.length);
  861.         line.length -= p - line.text;
  862.  
  863.         /* reset to start next cycle without reading a new line: */
  864.         cur_vec = vec;
  865.         cur_cmd = cur_vec->v;
  866.         n = cur_vec->v_length;
  867.         continue;
  868.           }
  869.  
  870.         case 'g':
  871.           line_copy(&hold, &line);
  872.           break;
  873.  
  874.         case 'G':
  875.           line_append(&hold, &line);
  876.           break;
  877.  
  878.         case 'h':
  879.           line_copy(&line, &hold);
  880.           break;
  881.  
  882.         case 'H':
  883.           line_append(&line, &hold);
  884.           break;
  885.  
  886.         case 'i':
  887.           output_line(cur_cmd->x.cmd_txt.text,
  888.               cur_cmd->x.cmd_txt.text_len, 0, stdout);
  889.           break;
  890.  
  891.         case 'l':
  892.           do_list();
  893.           break;
  894.  
  895.         case 'n':
  896.           if (!no_default_output)
  897.         output_line(line.text, line.length, line.chomped, stdout);
  898.           if (!read_pattern_space(input, 0))
  899.         return 1;
  900.           break;
  901.  
  902.         case 'N':
  903.           str_append(&line, "\n", 1);
  904.           if (!read_pattern_space(input, 1))
  905.         return 1;
  906.           break;
  907.  
  908.         case 'p':
  909.           output_line(line.text, line.length, line.chomped, stdout);
  910.           break;
  911.  
  912.         case 'P':
  913.           {
  914.         char *p = memchr(line.text, '\n', line.length);
  915.         output_line(line.text, p ? p - line.text : line.length,
  916.                 p ? 1 : line.chomped, stdout);
  917.           }
  918.           break;
  919.  
  920.         case 'q':
  921.           return 1;
  922.  
  923.         case 'r':
  924.           if (cur_cmd->x.rfile)
  925.         {
  926.           struct append_queue *aq = next_append_slot();
  927.           aq->rfile = cur_cmd->x.rfile;
  928.         }
  929.           break;
  930.  
  931.         case 's':
  932.           do_subst(&cur_cmd->x.cmd_regex);
  933.           break;
  934.  
  935.         case 't':
  936.           if (replaced)
  937.         {
  938.           replaced = 0;
  939.           if (cur_cmd->x.jump)
  940.             {
  941.               struct sed_label *j = cur_cmd->x.jump;
  942.               countT i = j->v_index;
  943.               cur_vec = j->v;
  944.               cur_cmd = cur_vec->v + i;
  945.               n = cur_vec->v_length - i;
  946.               continue;
  947.             }
  948.           return 0;
  949.         }
  950.           break;
  951.  
  952.         case 'w':
  953.           if (cur_cmd->x.wfile)
  954.         output_line(line.text, line.length,
  955.                 line.chomped, cur_cmd->x.wfile);
  956.           break;
  957.  
  958.         case 'x':
  959.           {
  960.         struct line temp;
  961.         memcpy(VCAST(VOID *)&temp, VCAST(VOID *)&line, sizeof line);
  962.         memcpy(VCAST(VOID *)&line, VCAST(VOID *)&hold, sizeof line);
  963.         memcpy(VCAST(VOID *)&hold, VCAST(VOID *)&temp, sizeof line);
  964.           }
  965.           break;
  966.  
  967.         case 'y':
  968.           {
  969.         unsigned char *p, *e;
  970.         p = CAST(unsigned char *)line.text;
  971.         for (e=p+line.length; p<e; ++p)
  972.           *p = cur_cmd->x.translate[*p];
  973.           }
  974.           break;
  975.  
  976.         case ':':
  977.           /* Executing labels is easy. */
  978.           break;
  979.  
  980.         case '=':
  981.           printf("%lu\n", CAST(unsigned long)input->line_number);
  982.           break;
  983.  
  984.         default:
  985.           panic("INTERNAL ERROR: Bad cmd %c", cur_cmd->cmd);
  986.         }
  987.     }
  988. #ifdef EXPERIMENTAL_DASH_N_OPTIMIZATION
  989. /* If our top-level program consists solely of commands with addr_is_num
  990.  * address then once we past the last mentioned line we should be able
  991.  * to quit if no_default_output is true, or otherwise quickly copy input
  992.  * to output.  Now whether this optimization is a win or not depends
  993.  * on how cheaply we can implement this for the cases where it doesn't
  994.  * help, as compared against how much time is saved.
  995.  * One semantic difference (which I think is an improvement) is
  996.  * that *this* version will terminate after printing line two
  997.  * in the script "yes | sed -n 2p".
  998.  */
  999.       else
  1000.     {
  1001.       /* can we ever match again? */
  1002.       if (cur_cmd->a1.addr_type == addr_is_num &&
  1003.           ((input->line_number < cur_cmd->a1.a.addr_number)
  1004.         != !cur_cmd->addr_bang))
  1005.         {
  1006.           /* skip all this next time */
  1007.           cur_cmd->a1.addr_type = addr_is_null;
  1008.           cur_cmd->addr_bang = 1;
  1009.           /* can we make an optimization? */
  1010.           if (cur_cmd->cmd == '{' || cur_cmd->cmd == '}'
  1011.             || cur_cmd->cmd == 'b' || cur_cmd->cmd == 't')
  1012.         {
  1013.           if (cur_vec == vec)
  1014.             --branches_in_top_level;
  1015.           cur_cmd->cmd = ':';    /* replace with no-op */
  1016.         }
  1017.           if (cur_vec == vec && branches_in_top_level == 0)
  1018.         {
  1019.           /* whew!  all that just so that we can get to here! */
  1020.           countT new_n = n;
  1021.           cur_cmd = shrink_program(cur_vec, cur_cmd, &new_n);
  1022.           n = new_n;
  1023.           if (!cur_cmd && no_default_output)
  1024.             return 1;
  1025.           continue;
  1026.         }
  1027.         }
  1028.     }
  1029. #endif /*EXPERIMENTAL_DASH_N_OPTIMIZATION*/
  1030.  
  1031.       /* these are buried down here so that a "continue" statement
  1032.      can skip them */
  1033.       ++cur_cmd;
  1034.       --n;
  1035.     }
  1036.     return 0;
  1037. }
  1038.  
  1039. static void
  1040. output_line(text, length, nl, fp)
  1041.   const char *text;
  1042.   size_t length;
  1043.   flagT nl;
  1044.   FILE *fp;
  1045. {
  1046.   ck_fwrite(text, 1, length, fp);
  1047.   if (nl)
  1048.     ck_fwrite("\n", 1, 1, fp);
  1049.   if (fp != stdout)
  1050.     ck_fflush(fp);
  1051. }
  1052.  
  1053.  
  1054. /* initialize a "struct line" buffer */
  1055. static void
  1056. line_init(buf, initial_size)
  1057.   struct line *buf;
  1058.   size_t initial_size;
  1059. {
  1060.   buf->text = MALLOC(initial_size, char);
  1061.   buf->active = NULL;
  1062.   buf->alloc = initial_size;
  1063.   buf->length = 0;
  1064.   buf->chomped = 1;
  1065. }
  1066.  
  1067. /* Copy the contents of the line 'from' into the line 'to'.
  1068.    This destroys the old contents of 'to'.  It will still work
  1069.    if the line 'from' contains NULs. */
  1070. static void
  1071. line_copy(from, to)
  1072.   struct line *from;
  1073.   struct line *to;
  1074. {
  1075.   if (to->alloc < from->length)
  1076.     {
  1077.       to->alloc = from->length;
  1078.       to->text = REALLOC(to->text, to->alloc, char);
  1079.     }
  1080.   memcpy(to->text, from->text, from->length);
  1081.   to->length = from->length;
  1082.   to->chomped = from->chomped;
  1083. }
  1084.  
  1085. /* Append 'length' bytes from 'string' to the line 'to'
  1086.    This routine *will* append NUL bytes without failing.  */
  1087. static void
  1088. str_append(to, string, length)
  1089.   struct line *to;
  1090.   const char *string;
  1091.   size_t length;
  1092. {
  1093.   if (to->alloc - to->length < length)
  1094.     resize_line(to, length);
  1095.   memcpy(to->text + to->length, string, length);
  1096.   to->length += length;
  1097. }
  1098.  
  1099. /* Append the contents of the line 'from' to the line 'to'.
  1100.    This routine will work even if the line 'from' contains nulls */
  1101. static void
  1102. line_append(from, to)
  1103.   struct line *from;
  1104.   struct line *to;
  1105. {
  1106.   str_append(to, "\n", 1);
  1107.   str_append(to, from->text, from->length);
  1108.   to->chomped = from->chomped;
  1109. }
  1110.  
  1111.  
  1112.  
  1113. static struct append_queue *
  1114. next_append_slot()
  1115. {
  1116.   struct append_queue *n = MALLOC(1, struct append_queue);
  1117.  
  1118.   n->rfile = NULL;
  1119.   n->text = NULL;
  1120.   n->textlen = 0;
  1121.   n->next = NULL;
  1122.  
  1123.   if (append_tail)
  1124.       append_tail->next = n;
  1125.   else
  1126.       append_head = n;
  1127.   return append_tail = n;
  1128. }
  1129.  
  1130. static void
  1131. dump_append_queue()
  1132. {
  1133.   struct append_queue *p, *q;
  1134.  
  1135.   for (p=append_head; p; p=q)
  1136.     {
  1137.       if (p->text)
  1138.       output_line(p->text, p->textlen, 0, stdout);
  1139.       if (p->rfile)
  1140.     {
  1141.       char buf[FREAD_BUFFER_SIZE];
  1142.       size_t cnt;
  1143.       FILE *fp;
  1144.  
  1145.       fp = fopen(p->rfile, "r");
  1146.       /* Not ck_fopen() because: "If _rfile_ does not exist or cannot be
  1147.          read, it shall be treated as if it were an empty file, causing
  1148.          no error condition."  IEEE Std 1003.2-1992 */
  1149.       if (fp)
  1150.         {
  1151.           while ((cnt = ck_fread(buf, 1, sizeof buf, fp)) > 0)
  1152.         ck_fwrite(buf, 1, cnt, stdout);
  1153.           fclose(fp);
  1154.         }
  1155.     }
  1156.       q = p->next;
  1157.       FREE(p);
  1158.     }
  1159.   append_head = append_tail = NULL;
  1160. }
  1161.  
  1162. #ifdef EXPERIMENTAL_DASH_N_OPTIMIZATION
  1163. static countT
  1164. count_branches(program)
  1165.   struct vector *program;
  1166. {
  1167.   struct sed_cmd *cur_cmd = program->v;
  1168.   countT isn_cnt = program->v_length;
  1169.   countT cnt = 0;
  1170.  
  1171.   while (isn_cnt-- > 0)
  1172.     {
  1173.       switch (cur_cmd->cmd)
  1174.     {
  1175.     case '{':
  1176.     case '}':
  1177.     case 'b':
  1178.     case 't':
  1179.       ++cnt;
  1180.     }
  1181.     }
  1182.   return cnt;
  1183. }
  1184.  
  1185. static struct sed_cmd *
  1186. shrink_program(vec, cur_cmd, n)
  1187.   struct vector *vec;
  1188.   struct sed_cmd *cur_cmd;
  1189.   countT *n;
  1190. {
  1191.   struct sed_cmd *v = vec->v;
  1192.   struct sed_cmd *last_cmd = v + vec->v_length;
  1193.   struct sed_cmd *p;
  1194.   countT cmd_cnt;
  1195.  
  1196.   for (p=v; p < cur_cmd; ++p)
  1197.     if (p->cmd != ':')
  1198.       *v++ = *p;
  1199.   cmd_cnt = v - vec->v;
  1200.  
  1201.   for (++p; p < last_cmd; ++p)
  1202.     if (p->cmd != ':')
  1203.       *v++ = *p;
  1204.   vec->v_length = v - vec->v;
  1205.  
  1206.   *n = vec->v_length - cmd_cnt;
  1207.   return 0 < vec->v_length ? cur_cmd-cmd_cnt : CAST(struct sed_cmd *)0;
  1208. }
  1209. #endif /*EXPERIMENTAL_DASH_N_OPTIMIZATION*/
  1210.  
  1211. #ifdef BOOTSTRAP
  1212. /* We can't be sure that the system we're boostrapping on has
  1213.    memchr(), and ../lib/memchr.c requires configuration knowledge
  1214.    about how many bits are in a `long'.  This implementation
  1215.    is far from ideal, but it should get us up-and-limping well
  1216.    enough to run the configure script, which is all that matters.
  1217. */
  1218. static VOID *
  1219. bootstrap_memchr(s, c, n)
  1220.   const VOID *s;
  1221.   int c;
  1222.   size_t n;
  1223. {
  1224.   char *p;
  1225.  
  1226.   for (p=(char *)s; n-- > 0; ++p)
  1227.     if (*p == c)
  1228.       return p;
  1229.   return CAST(VOID *)0;
  1230. }
  1231. #endif /*BOOTSTRAP*/
  1232.