usr.bin/sed/compile.c

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