usr.bin/sed/compile.c

   1 /*      $NetBSD: compile.c,v 1.35 2007/04/17 20:30:29 christos Exp $    */
   2
   3 /*-
   4  * Copyright (c) 1992, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Diomidis Spinellis of Imperial College, University of London.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 /*-
  36  * Copyright (c) 1992 Diomidis Spinellis.
  37  *
  38  * This code is derived from software contributed to Berkeley by
  39  * Diomidis Spinellis of Imperial College, University of London.
  40  *
  41  * Redistribution and use in source and binary forms, with or without
  42  * modification, are permitted provided that the following conditions
  43  * are met:
  44  * 1. Redistributions of source code must retain the above copyright
  45  *    notice, this list of conditions and the following disclaimer.
  46  * 2. Redistributions in binary form must reproduce the above copyright
  47  *    notice, this list of conditions and the following disclaimer in the
  48  *    documentation and/or other materials provided with the distribution.
  49  * 3. All advertising materials mentioning features or use of this software
  50  *    must display the following acknowledgement:
  51  *      This product includes software developed by the University of
  52  *      California, Berkeley and its contributors.
  53  * 4. Neither the name of the University nor the names of its contributors
  54  *    may be used to endorse or promote products derived from this software
  55  *    without specific prior written permission.
  56  *
  57  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  58  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  59  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  60  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  61  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  62  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  63  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  64  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  65  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  66  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  67  * SUCH DAMAGE.
  68  */
  69
  70 #if HAVE_NBTOOL_CONFIG_H
  71 #include "nbtool_config.h"
  72 #endif
  73
  74 #include <sys/cdefs.h>
  75 #ifndef lint
  76 #if 0
  77 static char sccsid[] = "@(#)compile.c   8.2 (Berkeley) 4/28/95";
  78 #else
  79 __RCSID("$NetBSD: compile.c,v 1.35 2007/04/17 20:30:29 christos Exp $");
  80 #endif
  81 #endif /* not lint */
  82
  83 #include <sys/types.h>
  84 #include <sys/stat.h>
  85
  86 #include <ctype.h>
  87 #include <errno.h>
  88 #include <fcntl.h>
  89 #include <limits.h>
  90 #include <regex.h>
  91 #include <stdio.h>
  92 #include <stdlib.h>
  93 #include <string.h>
  94
  95 #include "defs.h"
  96 #include "extern.h"
  97
  98 #ifndef _POSIX2_LINE_MAX
  99 #define _POSIX2_LINE_MAX (2 * BUFSIZ)
 100 #endif
 101
 102 #define LHSZ    128
 103 #define LHMASK  (LHSZ - 1)
 104 static struct labhash {
 105         struct  labhash *lh_next;
 106         u_int   lh_hash;
 107         struct  s_command *lh_cmd;
 108         int     lh_ref;
 109 } *labels[LHSZ];
 110
 111 static char      *compile_addr(char *, struct s_addr *);
 112 static char      *compile_ccl(char **, char *);
 113 static char      *compile_delimited(char *, char *);
 114 static char      *compile_flags(char *, struct s_subst *);
 115 static char      *compile_re(char *, regex_t **);
 116 static char      *compile_subst(char *, struct s_subst *);
 117 static char      *compile_text(void);
 118 static char      *compile_tr(char *, char **);
 119 static struct s_command
 120                 **compile_stream(struct s_command **);
 121 static char      *duptoeol(char *, const char *);
 122 static void       enterlabel(struct s_command *);
 123 static struct s_command
 124                  *findlabel(char *);
 125 static void       fixuplabel(struct s_command *, struct s_command *);
 126 static void       uselabel(void);
 127
 128 /*
 129  * Command specification.  This is used to drive the command parser.
 130  */
 131 struct s_format {
 132         char code;                              /* Command code */
 133         int naddr;                              /* Number of address args */
 134         enum e_args args;                       /* Argument type */
 135 };
 136
 137 static struct s_format cmd_fmts[] = {
 138         {'{', 2, GROUP},
 139         {'}', 0, ENDGROUP},
 140         {'a', 1, TEXT},
 141         {'b', 2, BRANCH},
 142         {'c', 2, TEXT},
 143         {'d', 2, EMPTY},
 144         {'D', 2, EMPTY},
 145         {'g', 2, EMPTY},
 146         {'G', 2, EMPTY},
 147         {'h', 2, EMPTY},
 148         {'H', 2, EMPTY},
 149         {'i', 1, TEXT},
 150         {'l', 2, EMPTY},
 151         {'n', 2, EMPTY},
 152         {'N', 2, EMPTY},
 153         {'p', 2, EMPTY},
 154         {'P', 2, EMPTY},
 155         {'q', 1, EMPTY},
 156         {'r', 1, RFILE},
 157         {'s', 2, SUBST},
 158         {'t', 2, BRANCH},
 159         {'w', 2, WFILE},
 160         {'x', 2, EMPTY},
 161         {'y', 2, TR},
 162         {'!', 2, NONSEL},
 163         {':', 0, LABEL},
 164         {'#', 0, COMMENT},
 165         {'=', 1, EMPTY},
 166         {'\0', 0, COMMENT},
 167 };
 168
 169 /* The compiled program. */
 170 struct s_command *prog;
 171
 172 /*
 173  * Compile the program into prog.
 174  * Initialise appends.
 175  */
 176 void
 177 compile(void)
 178 {
 179         *compile_stream(&prog) = NULL;
 180         fixuplabel(prog, NULL);
 181         uselabel();
 182         if (appendnum > 0)
 183                 appends = xmalloc(sizeof(struct s_appends) * appendnum);
 184         match = xmalloc((maxnsub + 1) * sizeof(regmatch_t));
 185 }
 186
 187 #define EATSPACE()                                              \
 188         while (*p && isascii((unsigned char)*p) &&              \
 189             isspace((unsigned char)*p))                         \
 190                 p++                                             \
 191
 192 static struct s_command **
 193 compile_stream(struct s_command **link)
 194 {
 195         char *p;
 196         static char lbuf[_POSIX2_LINE_MAX + 1]; /* To save stack */
 197         struct s_command *cmd, *cmd2, *stack;
 198         struct s_format *fp;
 199         int naddr;                              /* Number of addresses */
 200
 201         stack = 0;
 202         for (;;) {
 203                 if ((p = cu_fgets(lbuf, sizeof(lbuf))) == NULL) {
 204                         if (stack != 0)
 205                                 err(COMPILE, "unexpected EOF (pending }'s)");
 206                         return (link);
 207                 }
 208
 209 semicolon:      EATSPACE();
 210                 if (*p == '#' || *p == '\0')
 211                         continue;
 212                 else if (*p == ';') {
 213                         p++;
 214                         goto semicolon;
 215                 }
 216                 *link = cmd = xmalloc(sizeof(struct s_command));
 217                 link = &cmd->next;
 218                 cmd->nonsel = cmd->inrange = 0;
 219                 /* First parse the addresses */
 220                 naddr = 0;
 221
 222 /* Valid characters to start an address */
 223 #define addrchar(c)     (strchr("0123456789/\\$", (c)))
 224                 if (addrchar(*p)) {
 225                         naddr++;
 226                         cmd->a1 = xmalloc(sizeof(struct s_addr));
 227                         p = compile_addr(p, cmd->a1);
 228                         EATSPACE();                             /* EXTENSION */
 229                         if (*p == ',') {
 230                                 p++;
 231                                 EATSPACE();                     /* EXTENSION */
 232                                 naddr++;
 233                                 cmd->a2 = xmalloc(sizeof(struct s_addr));
 234                                 p = compile_addr(p, cmd->a2);
 235                                 EATSPACE();
 236                         } else
 237                                 cmd->a2 = 0;
 238                 } else
 239                         cmd->a1 = cmd->a2 = 0;
 240
 241 nonsel:         /* Now parse the command */
 242                 if (!*p)
 243                         err(COMPILE, "command expected");
 244                 cmd->code = *p;
 245                 for (fp = cmd_fmts; fp->code; fp++)
 246                         if (fp->code == *p)
 247                                 break;
 248                 if (!fp->code)
 249                         err(COMPILE, "invalid command code %c", *p);
 250                 if (naddr > fp->naddr)
 251                         err(COMPILE,
 252 "command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
 253                 switch (fp->args) {
 254                 case NONSEL:                    /* ! */
 255                         p++;
 256                         EATSPACE();
 257                         cmd->nonsel = ! cmd->nonsel;
 258                         goto nonsel;
 259                 case GROUP:                     /* { */
 260                         p++;
 261                         EATSPACE();
 262                         cmd->next = stack;
 263                         stack = cmd;
 264                         link = &cmd->u.c;
 265                         if (*p)
 266                                 goto semicolon;
 267                         break;
 268                 case ENDGROUP:
 269                         /*
 270                          * Short-circuit command processing, since end of
 271                          * group is really just a noop.
 272                          */
 273                         cmd->nonsel = 1;
 274                         if (stack == 0)
 275                                 err(COMPILE, "unexpected }");
 276                         cmd2 = stack;
 277                         stack = cmd2->next;
 278                         cmd2->next = cmd;
 279                         /*FALLTHROUGH*/
 280                 case EMPTY:             /* d D g G h H l n N p P q x = \0 */
 281                         p++;
 282                         EATSPACE();
 283                         if (*p == ';') {
 284                                 p++;
 285                                 link = &cmd->next;
 286                                 goto semicolon;
 287                         }
 288                         if (*p)
 289                                 err(COMPILE,
 290 "extra characters at the end of %c command", cmd->code);
 291                         break;
 292                 case TEXT:                      /* a c i */
 293                         p++;
 294                         EATSPACE();
 295                         if (*p != '\\')
 296                                 err(COMPILE,
 297 "command %c expects \\ followed by text", cmd->code);
 298                         p++;
 299                         EATSPACE();
 300                         if (*p)
 301                                 err(COMPILE,
 302 "extra characters after \\ at the end of %c command", cmd->code);
 303                         cmd->t = compile_text();
 304                         break;
 305                 case COMMENT:                   /* \0 # */
 306                         break;
 307                 case WFILE:                     /* w */
 308                         p++;
 309                         EATSPACE();
 310                         if (*p == '\0')
 311                                 err(COMPILE, "filename expected");
 312                         cmd->t = duptoeol(p, "w command");
 313                         if (aflag)
 314                                 cmd->u.fd = -1;
 315                         else if ((cmd->u.fd = open(p,
 316                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 317                             DEFFILEMODE)) == -1)
 318                                 err(FATAL, "%s: %s", p, strerror(errno));
 319                         break;
 320                 case RFILE:                     /* r */
 321                         p++;
 322                         EATSPACE();
 323                         if (*p == '\0')
 324                                 err(COMPILE, "filename expected");
 325                         else
 326                                 cmd->t = duptoeol(p, "read command");
 327                         break;
 328                 case BRANCH:                    /* b t */
 329                         p++;
 330                         EATSPACE();
 331                         if (*p == '\0')
 332                                 cmd->t = NULL;
 333                         else
 334                                 cmd->t = duptoeol(p, "branch");
 335                         break;
 336                 case LABEL:                     /* : */
 337                         p++;
 338                         EATSPACE();
 339                         cmd->t = duptoeol(p, "label");
 340                         if (strlen(p) == 0)
 341                                 err(COMPILE, "empty label");
 342                         enterlabel(cmd);
 343                         break;
 344                 case SUBST:                     /* s */
 345                         p++;
 346                         if (*p == '\0' || *p == '\\')
 347                                 err(COMPILE,
 348 "substitute pattern can not be delimited by newline or backslash");
 349                         cmd->u.s = xmalloc(sizeof(struct s_subst));
 350                         p = compile_re(p, &cmd->u.s->re);
 351                         if (p == NULL)
 352                                 err(COMPILE, "unterminated substitute pattern");
 353                         --p;
 354                         p = compile_subst(p, cmd->u.s);
 355                         p = compile_flags(p, cmd->u.s);
 356                         EATSPACE();
 357                         if (*p == ';') {
 358                                 p++;
 359                                 link = &cmd->next;
 360                                 goto semicolon;
 361                         }
 362                         break;
 363                 case TR:                        /* y */
 364                         p++;
 365                         p = compile_tr(p, (char **)(void *)&cmd->u.y);
 366                         EATSPACE();
 367                         if (*p == ';') {
 368                                 p++;
 369                                 link = &cmd->next;
 370                                 goto semicolon;
 371                         }
 372                         if (*p)
 373                                 err(COMPILE,
 374 "extra text at the end of a transform command");
 375                         break;
 376                 }
 377         }
 378 }
 379
 380 /*
 381  * Get a delimited string.  P points to the delimiter of the string; d points
 382  * to a buffer area.  Newline and delimiter escapes are processed; other
 383  * escapes are ignored.
 384  *
 385  * Returns a pointer to the first character after the final delimiter or NULL
 386  * in the case of a non-terminated string.  The character array d is filled
 387  * with the processed string.
 388  */
 389 static char *
 390 compile_delimited(char *p, char *d)
 391 {
 392         char c;
 393
 394         c = *p++;
 395         if (c == '\0')
 396                 return (NULL);
 397         else if (c == '\\')
 398                 err(COMPILE, "\\ can not be used as a string delimiter");
 399         else if (c == '\n')
 400                 err(COMPILE, "newline can not be used as a string delimiter");
 401         while (*p) {
 402                 if (*p == '[') {
 403                         if ((d = compile_ccl(&p, d)) == NULL)
 404                                 err(COMPILE, "unbalanced brackets ([])");
 405                         continue;
 406                 } else if (*p == '\\' && p[1] == '[') {
 407                         *d++ = *p++;
 408                 } else if (*p == '\\' && p[1] == c)
 409                         p++;
 410                 else if (*p == '\\' && p[1] == 'n') {
 411                         *d++ = '\n';
 412                         p += 2;
 413                         continue;
 414                 } else if (*p == '\\' && p[1] == '\\')
 415                         *d++ = *p++;
 416                 else if (*p == c) {
 417                         *d = '\0';
 418                         return (p + 1);
 419                 }
 420                 *d++ = *p++;
 421         }
 422         return (NULL);
 423 }
 424
 425
 426 /* compile_ccl: expand a POSIX character class */
 427 static char *
 428 compile_ccl(char **sp, char *t)
 429 {
 430         int c, d;
 431         char *s = *sp;
 432
 433         *t++ = *s++;
 434         if (*s == '^')
 435                 *t++ = *s++;
 436         if (*s == ']')
 437                 *t++ = *s++;
 438         for (; *s && (*t = *s) != ']'; s++, t++)
 439                 if (*s == '[' && ((d = *(s+1)) == '.' || d == ':' || d == '=')) {
 440                         *++t = *++s, t++, s++;
 441                         for (c = *s; (*t = *s) != ']' || c != d; s++, t++)
 442                                 if ((c = *s) == '\0')
 443                                         return NULL;
 444                 } else if (*s == '\\' && s[1] == 'n')
 445                             *t = '\n', s++;
 446         return (*s == ']') ? *sp = ++s, ++t : NULL;
 447 }
 448
 449 /*
 450  * Get a regular expression.  P points to the delimiter of the regular
 451  * expression; repp points to the address of a regexp pointer.  Newline
 452  * and delimiter escapes are processed; other escapes are ignored.
 453  * Returns a pointer to the first character after the final delimiter
 454  * or NULL in the case of a non terminated regular expression.  The regexp
 455  * pointer is set to the compiled regular expression.
 456  * Cflags are passed to regcomp.
 457  */
 458 static char *
 459 compile_re(char *p, regex_t **repp)
 460 {
 461         int eval;
 462         char re[_POSIX2_LINE_MAX + 1];
 463
 464         p = compile_delimited(p, re);
 465         if (p && strlen(re) == 0) {
 466                 *repp = NULL;
 467                 return (p);
 468         }
 469         *repp = xmalloc(sizeof(regex_t));
 470         if (p && (eval = regcomp(*repp, re, ere)) != 0)
 471                 err(COMPILE, "RE error: %s", strregerror(eval, *repp));
 472         if (maxnsub < (*repp)->re_nsub)
 473                 maxnsub = (*repp)->re_nsub;
 474         return (p);
 475 }
 476
 477 /*
 478  * Compile the substitution string of a regular expression and set res to
 479  * point to a saved copy of it.  Nsub is the number of parenthesized regular
 480  * expressions.
 481  */
 482 static char *
 483 compile_subst(char *p, struct s_subst *s)
 484 {
 485         static char lbuf[_POSIX2_LINE_MAX + 1];
 486         int asize, ref, size;
 487         char c, *text, *op, *sp;
 488         int sawesc = 0;
 489
 490         c = *p++;                       /* Terminator character */
 491         if (c == '\0')
 492                 return (NULL);
 493
 494         s->maxbref = 0;
 495         s->linenum = linenum;
 496         asize = 2 * _POSIX2_LINE_MAX + 1;
 497         text = xmalloc(asize);
 498         size = 0;
 499         do {
 500                 op = sp = text + size;
 501                 for (; *p; p++) {
 502                         if (*p == '\\' || sawesc) {
 503                                 /*
 504                                  * If this is a continuation from the last
 505                                  * buffer, we won't have a character to
 506                                  * skip over.
 507                                  */
 508                                 if (sawesc)
 509                                         sawesc = 0;
 510                                 else
 511                                         p++;
 512
 513                                 if (*p == '\0') {
 514                                         /*
 515                                          * This escaped character is continued
 516                                          * in the next part of the line.  Note
 517                                          * this fact, then cause the loop to
 518                                          * exit w/ normal EOL case and reenter
 519                                          * above with the new buffer.
 520                                          */
 521                                         sawesc = 1;
 522                                         p--;
 523                                         continue;
 524                                 } else if (strchr("123456789", *p) != NULL) {
 525                                         *sp++ = '\\';
 526                                         ref = *p - '0';
 527                                         if (s->re != NULL &&
 528                                             (size_t)ref > s->re->re_nsub)
 529                                                 err(COMPILE,
 530 "\\%c not defined in the RE", *p);
 531                                         if (s->maxbref < ref)
 532                                                 s->maxbref = ref;
 533                                 } else if (*p == '&' || *p == '\\')
 534                                         *sp++ = '\\';
 535                         } else if (*p == c) {
 536                                 p++;
 537                                 *sp++ = '\0';
 538                                 size += sp - op;
 539                                 s->new = xrealloc(text, size);
 540                                 return (p);
 541                         } else if (*p == '\n') {
 542                                 err(COMPILE,
 543 "unescaped newline inside substitute pattern");
 544                                 /* NOTREACHED */
 545                         }
 546                         *sp++ = *p;
 547                 }
 548                 size += sp - op;
 549                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 550                         asize *= 2;
 551                         text = xrealloc(text, asize);
 552                 }
 553         } while (cu_fgets(p = lbuf, sizeof(lbuf)));
 554         err(COMPILE, "unterminated substitute in regular expression");
 555         /* NOTREACHED */
 556         return (NULL);
 557 }
 558
 559 /*
 560  * Compile the flags of the s command
 561  */
 562 static char *
 563 compile_flags(char *p, struct s_subst *s)
 564 {
 565         int gn;                 /* True if we have seen g or n */
 566         char wfile[_POSIX2_LINE_MAX + 1], *q;
 567
 568         s->n = 1;                               /* Default */
 569         s->p = 0;
 570         s->wfile = NULL;
 571         s->wfd = -1;
 572         for (gn = 0;;) {
 573                 EATSPACE();                     /* EXTENSION */
 574                 switch (*p) {
 575                 case 'g':
 576                         if (gn)
 577                                 err(COMPILE,
 578 "more than one number or 'g' in substitute flags");
 579                         gn = 1;
 580                         s->n = 0;
 581                         break;
 582                 case '\0':
 583                 case '\n':
 584                 case ';':
 585                         return (p);
 586                 case 'p':
 587                         s->p = 1;
 588                         break;
 589                 case '1': case '2': case '3':
 590                 case '4': case '5': case '6':
 591                 case '7': case '8': case '9':
 592                         if (gn)
 593                                 err(COMPILE,
 594 "more than one number or 'g' in substitute flags");
 595                         gn = 1;
 596                         /* XXX Check for overflow */
 597                         s->n = (int)strtol(p, &p, 10);
 598                         p--;
 599                         break;
 600                 case 'w':
 601                         p++;
 602 #ifdef HISTORIC_PRACTICE
 603                         if (*p != ' ') {
 604                                 err(WARNING, "space missing before w wfile");
 605                                 return (p);
 606                         }
 607 #endif
 608                         EATSPACE();
 609                         q = wfile;
 610                         while (*p) {
 611                                 if (*p == '\n')
 612                                         break;
 613                                 *q++ = *p++;
 614                         }
 615                         *q = '\0';
 616                         if (q == wfile)
 617                                 err(COMPILE, "no wfile specified");
 618                         s->wfile = strdup(wfile);
 619                         if (!aflag && (s->wfd = open(wfile,
 620                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 621                             DEFFILEMODE)) == -1)
 622                                 err(FATAL, "%s: %s", wfile, strerror(errno));
 623                         return (p);
 624                 default:
 625                         err(COMPILE,
 626                             "bad flag in substitute command: '%c'", *p);
 627                         break;
 628                 }
 629                 p++;
 630         }
 631 }
 632
 633 /*
 634  * Compile a translation set of strings into a lookup table.
 635  */
 636 static char *
 637 compile_tr(char *p, char **transtab)
 638 {
 639         int i;
 640         char *lt, *op, *np;
 641         char old[_POSIX2_LINE_MAX + 1];
 642         char new[_POSIX2_LINE_MAX + 1];
 643
 644         if (*p == '\0' || *p == '\\')
 645                 err(COMPILE,
 646 "transform pattern can not be delimited by newline or backslash");
 647         p = compile_delimited(p, old);
 648         if (p == NULL) {
 649                 err(COMPILE, "unterminated transform source string");
 650                 return (NULL);
 651         }
 652         p = compile_delimited(--p, new);
 653         if (p == NULL) {
 654                 err(COMPILE, "unterminated transform target string");
 655                 return (NULL);
 656         }
 657         EATSPACE();
 658         if (strlen(new) != strlen(old)) {
 659                 err(COMPILE, "transform strings are not the same length");
 660                 return (NULL);
 661         }
 662         /* We assume characters are 8 bits */
 663         lt = xmalloc(UCHAR_MAX+1);
 664         for (i = 0; i <= UCHAR_MAX; i++)
 665                 lt[i] = (char)i;
 666         for (op = old, np = new; *op; op++, np++)
 667                 lt[(u_char)*op] = *np;
 668         *transtab = lt;
 669         return (p);
 670 }
 671
 672 /*
 673  * Compile the text following an a, c, or i command.
 674  */
 675 static char *
 676 compile_text(void)
 677 {
 678         int asize, size;
 679         char *text, *p, *op, *s;
 680         char lbuf[_POSIX2_LINE_MAX + 1];
 681
 682         asize = 2 * _POSIX2_LINE_MAX + 1;
 683         text = xmalloc(asize);
 684         size = 0;
 685         while (cu_fgets(lbuf, sizeof(lbuf))) {
 686                 op = s = text + size;
 687                 p = lbuf;
 688                 for (; *p; p++) {
 689                         if (*p == '\\')
 690                                 p++;
 691                         *s++ = *p;
 692                 }
 693                 size += s - op;
 694                 if (p[-2] != '\\') {
 695                         *s = '\0';
 696                         break;
 697                 }
 698                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 699                         asize *= 2;
 700                         text = xrealloc(text, asize);
 701                 }
 702         }
 703         return (xrealloc(text, size + 1));
 704 }
 705
 706 /*
 707  * Get an address and return a pointer to the first character after
 708  * it.  Fill the structure pointed to according to the address.
 709  */
 710 static char *
 711 compile_addr(char *p, struct s_addr *a)
 712 {
 713         char *end;
 714
 715         switch (*p) {
 716         case '\\':                              /* Context address */
 717                 ++p;
 718                 /* FALLTHROUGH */
 719         case '/':                               /* Context address */
 720                 p = compile_re(p, &a->u.r);
 721                 if (p == NULL)
 722                         err(COMPILE, "unterminated regular expression");
 723                 a->type = AT_RE;
 724                 return (p);
 725
 726         case '$':                               /* Last line */
 727                 a->type = AT_LAST;
 728                 return (p + 1);
 729                                                 /* Line number */
 730         case '0': case '1': case '2': case '3': case '4':
 731         case '5': case '6': case '7': case '8': case '9':
 732                 a->type = AT_LINE;
 733                 a->u.l = strtol(p, &end, 10);
 734                 return (end);
 735         default:
 736                 err(COMPILE, "expected context address");
 737                 return (NULL);
 738         }
 739 }
 740
 741 /*
 742  * duptoeol --
 743  *      Return a copy of all the characters up to \n or \0.
 744  */
 745 static char *
 746 duptoeol(char *s, const char *ctype)
 747 {
 748         size_t len;
 749         int ws;
 750         char *start;
 751
 752         ws = 0;
 753         for (start = s; *s != '\0' && *s != '\n'; ++s)
 754                 ws = isspace((unsigned char)*s);
 755         *s = '\0';
 756         if (ws)
 757                 err(WARNING, "whitespace after %s", ctype);
 758         len = s - start + 1;
 759         return (memmove(xmalloc(len), start, len));
 760 }
 761
 762 /*
 763  * Convert goto label names to addresses, and count a and r commands, in
 764  * the given subset of the script.  Free the memory used by labels in b
 765  * and t commands (but not by :).
 766  *
 767  * TODO: Remove } nodes
 768  */
 769 static void
 770 fixuplabel(struct s_command *cp, struct s_command *end)
 771 {
 772
 773         for (; cp != end; cp = cp->next)
 774                 switch (cp->code) {
 775                 case 'a':
 776                 case 'r':
 777                         appendnum++;
 778                         break;
 779                 case 'b':
 780                 case 't':
 781                         /* Resolve branch target. */
 782                         if (cp->t == NULL) {
 783                                 cp->u.c = NULL;
 784                                 break;
 785                         }
 786                         if ((cp->u.c = findlabel(cp->t)) == NULL)
 787                                 err(COMPILE2, "undefined label '%s'", cp->t);
 788                         free(cp->t);
 789                         break;
 790                 case '{':
 791                         /* Do interior commands. */
 792                         fixuplabel(cp->u.c, cp->next);
 793                         break;
 794                 }
 795 }
 796
 797 /*
 798  * Associate the given command label for later lookup.
 799  */
 800 static void
 801 enterlabel(struct s_command *cp)
 802 {
 803         struct labhash **lhp, *lh;
 804         u_char *p;
 805         u_int h, c;
 806
 807         for (h = 0, p = (u_char *)cp->t; (c = *p) != 0; p++)
 808                 h = (h << 5) + h + c;
 809         lhp = &labels[h & LHMASK];
 810         for (lh = *lhp; lh != NULL; lh = lh->lh_next)
 811                 if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
 812                         err(COMPILE2, "duplicate label '%s'", cp->t);
 813         lh = xmalloc(sizeof *lh);
 814         lh->lh_next = *lhp;
 815         lh->lh_hash = h;
 816         lh->lh_cmd = cp;
 817         lh->lh_ref = 0;
 818         *lhp = lh;
 819 }
 820
 821 /*
 822  * Find the label contained in the command l in the command linked
 823  * list cp.  L is excluded from the search.  Return NULL if not found.
 824  */
 825 static struct s_command *
 826 findlabel(char *name)
 827 {
 828         struct labhash *lh;
 829         u_char *p;
 830         u_int h, c;
 831
 832         for (h = 0, p = (u_char *)name; (c = *p) != 0; p++)
 833                 h = (h << 5) + h + c;
 834         for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
 835                 if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
 836                         lh->lh_ref = 1;
 837                         return (lh->lh_cmd);
 838                 }
 839         }
 840         return (NULL);
 841 }
 842
 843 /*
 844  * Warn about any unused labels.  As a side effect, release the label hash
 845  * table space.
 846  */
 847 static void
 848 uselabel(void)
 849 {
 850         struct labhash *lh, *next;
 851         int i;
 852
 853         for (i = 0; i < LHSZ; i++) {
 854                 for (lh = labels[i]; lh != NULL; lh = next) {
 855                         next = lh->lh_next;
 856                         if (!lh->lh_ref)
 857                                 err(WARNING, "unused label '%s'",
 858                                     lh->lh_cmd->t);
 859                         free(lh);
 860                 }
 861         }
 862 }