usr.bin/sed/compile.c

   1 /*      $NetBSD: compile.c,v 1.37 2010/02/19 16:35:27 tnn 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.37 2010/02/19 16:35:27 tnn 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;      /* To avoid excessive malloc calls */
 197         static size_t bufsize;
 198         struct s_command *cmd, *cmd2, *stack;
 199         struct s_format *fp;
 200         int naddr;                              /* Number of addresses */
 201
 202         stack = 0;
 203         for (;;) {
 204                 if ((p = cu_fgets(&lbuf, &bufsize)) == NULL) {
 205                         if (stack != 0)
 206                                 err(COMPILE, "unexpected EOF (pending }'s)");
 207                         return (link);
 208                 }
 209
 210 semicolon:      EATSPACE();
 211                 if (*p == '#' || *p == '\0')
 212                         continue;
 213                 else if (*p == ';') {
 214                         p++;
 215                         goto semicolon;
 216                 }
 217                 *link = cmd = xmalloc(sizeof(struct s_command));
 218                 link = &cmd->next;
 219                 cmd->nonsel = cmd->inrange = 0;
 220                 /* First parse the addresses */
 221                 naddr = 0;
 222
 223 /* Valid characters to start an address */
 224 #define addrchar(c)     (strchr("0123456789/\\$", (c)))
 225                 if (addrchar(*p)) {
 226                         naddr++;
 227                         cmd->a1 = xmalloc(sizeof(struct s_addr));
 228                         p = compile_addr(p, cmd->a1);
 229                         EATSPACE();                             /* EXTENSION */
 230                         if (*p == ',') {
 231                                 p++;
 232                                 EATSPACE();                     /* EXTENSION */
 233                                 naddr++;
 234                                 cmd->a2 = xmalloc(sizeof(struct s_addr));
 235                                 p = compile_addr(p, cmd->a2);
 236                                 EATSPACE();
 237                         } else
 238                                 cmd->a2 = 0;
 239                 } else
 240                         cmd->a1 = cmd->a2 = 0;
 241
 242 nonsel:         /* Now parse the command */
 243                 if (!*p)
 244                         err(COMPILE, "command expected");
 245                 cmd->code = *p;
 246                 for (fp = cmd_fmts; fp->code; fp++)
 247                         if (fp->code == *p)
 248                                 break;
 249                 if (!fp->code)
 250                         err(COMPILE, "invalid command code %c", *p);
 251                 if (naddr > fp->naddr)
 252                         err(COMPILE,
 253 "command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
 254                 switch (fp->args) {
 255                 case NONSEL:                    /* ! */
 256                         p++;
 257                         EATSPACE();
 258                         cmd->nonsel = ! cmd->nonsel;
 259                         goto nonsel;
 260                 case GROUP:                     /* { */
 261                         p++;
 262                         EATSPACE();
 263                         cmd->next = stack;
 264                         stack = cmd;
 265                         link = &cmd->u.c;
 266                         if (*p)
 267                                 goto semicolon;
 268                         break;
 269                 case ENDGROUP:
 270                         /*
 271                          * Short-circuit command processing, since end of
 272                          * group is really just a noop.
 273                          */
 274                         cmd->nonsel = 1;
 275                         if (stack == 0)
 276                                 err(COMPILE, "unexpected }");
 277                         cmd2 = stack;
 278                         stack = cmd2->next;
 279                         cmd2->next = cmd;
 280                         /*FALLTHROUGH*/
 281                 case EMPTY:             /* d D g G h H l n N p P q x = \0 */
 282                         p++;
 283                         EATSPACE();
 284                         if (*p == ';') {
 285                                 p++;
 286                                 link = &cmd->next;
 287                                 goto semicolon;
 288                         }
 289                         if (*p)
 290                                 err(COMPILE,
 291 "extra characters at the end of %c command", cmd->code);
 292                         break;
 293                 case TEXT:                      /* a c i */
 294                         p++;
 295                         EATSPACE();
 296                         if (*p != '\\')
 297                                 err(COMPILE,
 298 "command %c expects \\ followed by text", cmd->code);
 299                         p++;
 300                         EATSPACE();
 301                         if (*p)
 302                                 err(COMPILE,
 303 "extra characters after \\ at the end of %c command", cmd->code);
 304                         cmd->t = compile_text();
 305                         break;
 306                 case COMMENT:                   /* \0 # */
 307                         break;
 308                 case WFILE:                     /* w */
 309                         p++;
 310                         EATSPACE();
 311                         if (*p == '\0')
 312                                 err(COMPILE, "filename expected");
 313                         cmd->t = duptoeol(p, "w command");
 314                         if (aflag)
 315                                 cmd->u.fd = -1;
 316                         else if ((cmd->u.fd = open(p,
 317                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 318                             DEFFILEMODE)) == -1)
 319                                 err(FATAL, "%s: %s", p, strerror(errno));
 320                         break;
 321                 case RFILE:                     /* r */
 322                         p++;
 323                         EATSPACE();
 324                         if (*p == '\0')
 325                                 err(COMPILE, "filename expected");
 326                         else
 327                                 cmd->t = duptoeol(p, "read command");
 328                         break;
 329                 case BRANCH:                    /* b t */
 330                         p++;
 331                         EATSPACE();
 332                         if (*p == '\0')
 333                                 cmd->t = NULL;
 334                         else
 335                                 cmd->t = duptoeol(p, "branch");
 336                         break;
 337                 case LABEL:                     /* : */
 338                         p++;
 339                         EATSPACE();
 340                         cmd->t = duptoeol(p, "label");
 341                         if (strlen(p) == 0)
 342                                 err(COMPILE, "empty label");
 343                         enterlabel(cmd);
 344                         break;
 345                 case SUBST:                     /* s */
 346                         p++;
 347                         if (*p == '\0' || *p == '\\')
 348                                 err(COMPILE,
 349 "substitute pattern can not be delimited by newline or backslash");
 350                         cmd->u.s = xmalloc(sizeof(struct s_subst));
 351                         p = compile_re(p, &cmd->u.s->re);
 352                         if (p == NULL)
 353                                 err(COMPILE, "unterminated substitute pattern");
 354                         --p;
 355                         p = compile_subst(p, cmd->u.s);
 356                         p = compile_flags(p, cmd->u.s);
 357                         EATSPACE();
 358                         if (*p == ';') {
 359                                 p++;
 360                                 link = &cmd->next;
 361                                 goto semicolon;
 362                         }
 363                         break;
 364                 case TR:                        /* y */
 365                         p++;
 366                         p = compile_tr(p, (char **)(void *)&cmd->u.y);
 367                         EATSPACE();
 368                         if (*p == ';') {
 369                                 p++;
 370                                 link = &cmd->next;
 371                                 goto semicolon;
 372                         }
 373                         if (*p)
 374                                 err(COMPILE,
 375 "extra text at the end of a transform command");
 376                         break;
 377                 }
 378         }
 379 }
 380
 381 /*
 382  * Get a delimited string.  P points to the delimiter of the string; d points
 383  * to a buffer area.  Newline and delimiter escapes are processed; other
 384  * escapes are ignored.
 385  *
 386  * Returns a pointer to the first character after the final delimiter or NULL
 387  * in the case of a non-terminated string.  The character array d is filled
 388  * with the processed string.
 389  */
 390 static char *
 391 compile_delimited(char *p, char *d)
 392 {
 393         char c;
 394
 395         c = *p++;
 396         if (c == '\0')
 397                 return (NULL);
 398         else if (c == '\\')
 399                 err(COMPILE, "\\ can not be used as a string delimiter");
 400         else if (c == '\n')
 401                 err(COMPILE, "newline can not be used as a string delimiter");
 402         while (*p) {
 403                 if (*p == '[') {
 404                         if ((d = compile_ccl(&p, d)) == NULL)
 405                                 err(COMPILE, "unbalanced brackets ([])");
 406                         continue;
 407                 } else if (*p == '\\' && p[1] == '[') {
 408                         *d++ = *p++;
 409                 } else if (*p == '\\' && p[1] == c)
 410                         p++;
 411                 else if (*p == '\\' && p[1] == 'n') {
 412                         *d++ = '\n';
 413                         p += 2;
 414                         continue;
 415                 } else if (*p == '\\' && p[1] == '\\')
 416                         *d++ = *p++;
 417                 else if (*p == c) {
 418                         *d = '\0';
 419                         return (p + 1);
 420                 }
 421                 *d++ = *p++;
 422         }
 423         return (NULL);
 424 }
 425
 426
 427 /* compile_ccl: expand a POSIX character class */
 428 static char *
 429 compile_ccl(char **sp, char *t)
 430 {
 431         int c, d;
 432         char *s = *sp;
 433
 434         *t++ = *s++;
 435         if (*s == '^')
 436                 *t++ = *s++;
 437         if (*s == ']')
 438                 *t++ = *s++;
 439         for (; *s && (*t = *s) != ']'; s++, t++)
 440                 if (*s == '[' && ((d = *(s+1)) == '.' || d == ':' || d == '=')) {
 441                         *++t = *++s, t++, s++;
 442                         for (c = *s; (*t = *s) != ']' || c != d; s++, t++)
 443                                 if ((c = *s) == '\0')
 444                                         return NULL;
 445                 } else if (*s == '\\' && s[1] == 'n')
 446                             *t = '\n', s++;
 447         return (*s == ']') ? *sp = ++s, ++t : NULL;
 448 }
 449
 450 /*
 451  * Get a regular expression.  P points to the delimiter of the regular
 452  * expression; repp points to the address of a regexp pointer.  Newline
 453  * and delimiter escapes are processed; other escapes are ignored.
 454  * Returns a pointer to the first character after the final delimiter
 455  * or NULL in the case of a non terminated regular expression.  The regexp
 456  * pointer is set to the compiled regular expression.
 457  * Cflags are passed to regcomp.
 458  */
 459 static char *
 460 compile_re(char *p, regex_t **repp)
 461 {
 462         int eval;
 463         char *re;
 464
 465         re = xmalloc(strlen(p) + 1); /* strlen(re) <= strlen(p) */
 466         p = compile_delimited(p, re);
 467         if (p && strlen(re) == 0) {
 468                 *repp = NULL;
 469                 free(re);
 470                 return (p);
 471         }
 472         *repp = xmalloc(sizeof(regex_t));
 473         if (p && (eval = regcomp(*repp, re, ere)) != 0)
 474                 err(COMPILE, "RE error: %s", strregerror(eval, *repp));
 475         if (maxnsub < (*repp)->re_nsub)
 476                 maxnsub = (*repp)->re_nsub;
 477         return (p);
 478 }
 479
 480 /*
 481  * Compile the substitution string of a regular expression and set res to
 482  * point to a saved copy of it.  Nsub is the number of parenthesized regular
 483  * expressions.
 484  */
 485 static char *
 486 compile_subst(char *p, struct s_subst *s)
 487 {
 488         static char *lbuf;
 489         static size_t bufsize;
 490         int asize, ref, size, len;
 491         char c, *text, *op, *sp;
 492         int sawesc = 0;
 493
 494         c = *p++;                       /* Terminator character */
 495         if (c == '\0')
 496                 return (NULL);
 497
 498         s->maxbref = 0;
 499         s->linenum = linenum;
 500         text = NULL;
 501         asize = size = 0;
 502         do {
 503                 len = ROUNDLEN(strlen(p) + 1);
 504                 if (asize - size < len) {
 505                         do {
 506                                 asize += len;
 507                         } while (asize - size < len);
 508                         text = xrealloc(text, asize);
 509                 }
 510                 op = sp = text + size;
 511                 for (; *p; p++) {
 512                         if (*p == '\\' || sawesc) {
 513                                 /*
 514                                  * If this is a continuation from the last
 515                                  * buffer, we won't have a character to
 516                                  * skip over.
 517                                  */
 518                                 if (sawesc)
 519                                         sawesc = 0;
 520                                 else
 521                                         p++;
 522
 523                                 if (*p == '\0') {
 524                                         /*
 525                                          * This escaped character is continued
 526                                          * in the next part of the line.  Note
 527                                          * this fact, then cause the loop to
 528                                          * exit w/ normal EOL case and reenter
 529                                          * above with the new buffer.
 530                                          */
 531                                         sawesc = 1;
 532                                         p--;
 533                                         continue;
 534                                 } else if (strchr("123456789", *p) != NULL) {
 535                                         *sp++ = '\\';
 536                                         ref = *p - '0';
 537                                         if (s->re != NULL &&
 538                                             (size_t)ref > s->re->re_nsub)
 539                                                 err(COMPILE,
 540 "\\%c not defined in the RE", *p);
 541                                         if (s->maxbref < ref)
 542                                                 s->maxbref = ref;
 543                                 } else if (*p == '&' || *p == '\\')
 544                                         *sp++ = '\\';
 545                         } else if (*p == c) {
 546                                 p++;
 547                                 *sp++ = '\0';
 548                                 size += sp - op;
 549                                 s->new = xrealloc(text, size);
 550                                 return (p);
 551                         } else if (*p == '\n') {
 552                                 err(COMPILE,
 553 "unescaped newline inside substitute pattern");
 554                                 /* NOTREACHED */
 555                         }
 556                         *sp++ = *p;
 557                 }
 558                 size += sp - op;
 559         } while ((p = cu_fgets(&lbuf, &bufsize)));
 560         err(COMPILE, "unterminated substitute in regular expression");
 561         /* NOTREACHED */
 562         return (NULL);
 563 }
 564
 565 /*
 566  * Compile the flags of the s command
 567  */
 568 static char *
 569 compile_flags(char *p, struct s_subst *s)
 570 {
 571         int gn;                 /* True if we have seen g or n */
 572         char wfile[PATH_MAX], *q;
 573
 574         s->n = 1;                               /* Default */
 575         s->p = 0;
 576         s->wfile = NULL;
 577         s->wfd = -1;
 578         for (gn = 0;;) {
 579                 EATSPACE();                     /* EXTENSION */
 580                 switch (*p) {
 581                 case 'g':
 582                         if (gn)
 583                                 err(COMPILE,
 584 "more than one number or 'g' in substitute flags");
 585                         gn = 1;
 586                         s->n = 0;
 587                         break;
 588                 case '\0':
 589                 case '\n':
 590                 case ';':
 591                         return (p);
 592                 case 'p':
 593                         s->p = 1;
 594                         break;
 595                 case '1': case '2': case '3':
 596                 case '4': case '5': case '6':
 597                 case '7': case '8': case '9':
 598                         if (gn)
 599                                 err(COMPILE,
 600 "more than one number or 'g' in substitute flags");
 601                         gn = 1;
 602                         /* XXX Check for overflow */
 603                         s->n = (int)strtol(p, &p, 10);
 604                         p--;
 605                         break;
 606                 case 'w':
 607                         p++;
 608 #ifdef HISTORIC_PRACTICE
 609                         if (*p != ' ') {
 610                                 err(WARNING, "space missing before w wfile");
 611                                 return (p);
 612                         }
 613 #endif
 614                         EATSPACE();
 615                         q = wfile;
 616                         while (*p) {
 617                                 if (*p == '\n')
 618                                         break;
 619                                 *q++ = *p++;
 620                         }
 621                         *q = '\0';
 622                         if (q == wfile)
 623                                 err(COMPILE, "no wfile specified");
 624                         s->wfile = strdup(wfile);
 625                         if (!aflag && (s->wfd = open(wfile,
 626                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 627                             DEFFILEMODE)) == -1)
 628                                 err(FATAL, "%s: %s", wfile, strerror(errno));
 629                         return (p);
 630                 default:
 631                         err(COMPILE,
 632                             "bad flag in substitute command: '%c'", *p);
 633                         break;
 634                 }
 635                 p++;
 636         }
 637 }
 638
 639 /*
 640  * Compile a translation set of strings into a lookup table.
 641  */
 642 static char *
 643 compile_tr(char *p, char **transtab)
 644 {
 645         int i;
 646         char *lt, *op, *np;
 647         char *old = NULL, *new = NULL;
 648
 649         if (*p == '\0' || *p == '\\')
 650                 err(COMPILE,
 651 "transform pattern can not be delimited by newline or backslash");
 652         old = xmalloc(strlen(p) + 1);
 653         p = compile_delimited(p, old);
 654         if (p == NULL) {
 655                 err(COMPILE, "unterminated transform source string");
 656                 goto bad;
 657         }
 658         new = xmalloc(strlen(p) + 1);
 659         p = compile_delimited(--p, new);
 660         if (p == NULL) {
 661                 err(COMPILE, "unterminated transform target string");
 662                 goto bad;
 663         }
 664         EATSPACE();
 665         if (strlen(new) != strlen(old)) {
 666                 err(COMPILE, "transform strings are not the same length");
 667                 goto bad;
 668         }
 669         /* We assume characters are 8 bits */
 670         lt = xmalloc(UCHAR_MAX+1);
 671         for (i = 0; i <= UCHAR_MAX; i++)
 672                 lt[i] = (char)i;
 673         for (op = old, np = new; *op; op++, np++)
 674                 lt[(u_char)*op] = *np;
 675         *transtab = lt;
 676         free(old);
 677         free(new);
 678         return (p);
 679 bad:
 680         free(old);
 681         free(new);
 682         return (NULL);
 683 }
 684
 685 /*
 686  * Compile the text following an a, c, or i command.
 687  */
 688 static char *
 689 compile_text(void)
 690 {
 691         int asize, size, len;
 692         char *lbuf, *text, *p, *op, *s;
 693         size_t bufsize;
 694
 695         lbuf = text = NULL;
 696         asize = size = 0;
 697         while ((p = cu_fgets(&lbuf, &bufsize))) {
 698                 len = ROUNDLEN(strlen(p) + 1);
 699                 if (asize - size < len) {
 700                         do {
 701                                 asize += len;
 702                         } while (asize - size < len);
 703                         text = xrealloc(text, asize);
 704                 }
 705                 op = s = text + size;
 706                 for (; *p; p++) {
 707                         if (*p == '\\')
 708                                 p++;
 709                         *s++ = *p;
 710                 }
 711                 size += s - op;
 712                 if (p[-2] != '\\') {
 713                         *s = '\0';
 714                         break;
 715                 }
 716         }
 717         free(lbuf);
 718         return (xrealloc(text, size + 1));
 719 }
 720
 721 /*
 722  * Get an address and return a pointer to the first character after
 723  * it.  Fill the structure pointed to according to the address.
 724  */
 725 static char *
 726 compile_addr(char *p, struct s_addr *a)
 727 {
 728         char *end;
 729
 730         switch (*p) {
 731         case '\\':                              /* Context address */
 732                 ++p;
 733                 /* FALLTHROUGH */
 734         case '/':                               /* Context address */
 735                 p = compile_re(p, &a->u.r);
 736                 if (p == NULL)
 737                         err(COMPILE, "unterminated regular expression");
 738                 a->type = AT_RE;
 739                 return (p);
 740
 741         case '$':                               /* Last line */
 742                 a->type = AT_LAST;
 743                 return (p + 1);
 744                                                 /* Line number */
 745         case '0': case '1': case '2': case '3': case '4':
 746         case '5': case '6': case '7': case '8': case '9':
 747                 a->type = AT_LINE;
 748                 a->u.l = strtol(p, &end, 10);
 749                 return (end);
 750         default:
 751                 err(COMPILE, "expected context address");
 752                 return (NULL);
 753         }
 754 }
 755
 756 /*
 757  * duptoeol --
 758  *      Return a copy of all the characters up to \n or \0.
 759  */
 760 static char *
 761 duptoeol(char *s, const char *ctype)
 762 {
 763         size_t len;
 764         int ws;
 765         char *start;
 766
 767         ws = 0;
 768         for (start = s; *s != '\0' && *s != '\n'; ++s)
 769                 ws = isspace((unsigned char)*s);
 770         *s = '\0';
 771         if (ws)
 772                 err(WARNING, "whitespace after %s", ctype);
 773         len = s - start + 1;
 774         return (memmove(xmalloc(len), start, len));
 775 }
 776
 777 /*
 778  * Convert goto label names to addresses, and count a and r commands, in
 779  * the given subset of the script.  Free the memory used by labels in b
 780  * and t commands (but not by :).
 781  *
 782  * TODO: Remove } nodes
 783  */
 784 static void
 785 fixuplabel(struct s_command *cp, struct s_command *end)
 786 {
 787
 788         for (; cp != end; cp = cp->next)
 789                 switch (cp->code) {
 790                 case 'a':
 791                 case 'r':
 792                         appendnum++;
 793                         break;
 794                 case 'b':
 795                 case 't':
 796                         /* Resolve branch target. */
 797                         if (cp->t == NULL) {
 798                                 cp->u.c = NULL;
 799                                 break;
 800                         }
 801                         if ((cp->u.c = findlabel(cp->t)) == NULL)
 802                                 err(COMPILE2, "undefined label '%s'", cp->t);
 803                         free(cp->t);
 804                         break;
 805                 case '{':
 806                         /* Do interior commands. */
 807                         fixuplabel(cp->u.c, cp->next);
 808                         break;
 809                 }
 810 }
 811
 812 /*
 813  * Associate the given command label for later lookup.
 814  */
 815 static void
 816 enterlabel(struct s_command *cp)
 817 {
 818         struct labhash **lhp, *lh;
 819         u_char *p;
 820         u_int h, c;
 821
 822         for (h = 0, p = (u_char *)cp->t; (c = *p) != 0; p++)
 823                 h = (h << 5) + h + c;
 824         lhp = &labels[h & LHMASK];
 825         for (lh = *lhp; lh != NULL; lh = lh->lh_next)
 826                 if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
 827                         err(COMPILE2, "duplicate label '%s'", cp->t);
 828         lh = xmalloc(sizeof *lh);
 829         lh->lh_next = *lhp;
 830         lh->lh_hash = h;
 831         lh->lh_cmd = cp;
 832         lh->lh_ref = 0;
 833         *lhp = lh;
 834 }
 835
 836 /*
 837  * Find the label contained in the command l in the command linked
 838  * list cp.  L is excluded from the search.  Return NULL if not found.
 839  */
 840 static struct s_command *
 841 findlabel(char *name)
 842 {
 843         struct labhash *lh;
 844         u_char *p;
 845         u_int h, c;
 846
 847         for (h = 0, p = (u_char *)name; (c = *p) != 0; p++)
 848                 h = (h << 5) + h + c;
 849         for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
 850                 if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
 851                         lh->lh_ref = 1;
 852                         return (lh->lh_cmd);
 853                 }
 854         }
 855         return (NULL);
 856 }
 857
 858 /*
 859  * Warn about any unused labels.  As a side effect, release the label hash
 860  * table space.
 861  */
 862 static void
 863 uselabel(void)
 864 {
 865         struct labhash *lh, *next;
 866         int i;
 867
 868         for (i = 0; i < LHSZ; i++) {
 869                 for (lh = labels[i]; lh != NULL; lh = next) {
 870                         next = lh->lh_next;
 871                         if (!lh->lh_ref)
 872                                 err(WARNING, "unused label '%s'",
 873                                     lh->lh_cmd->t);
 874                         free(lh);
 875                 }
 876         }
 877 }