usr/src/cmd/sed/compile.c

   1 /*
   2  * Copyright 2010 Nexenta Systems, Inc.  All rights reserved.
   3  * Copyright (c) 1992 Diomidis Spinellis.
   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  * 4. 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 #include <sys/types.h>
  36 #include <sys/stat.h>
  37
  38 #include <ctype.h>
  39 #include <err.h>
  40 #include <errno.h>
  41 #include <fcntl.h>
  42 #include <limits.h>
  43 #include <regex.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <wchar.h>
  48 #include <libintl.h>
  49 #include <note.h>
  50
  51 #include "defs.h"
  52 #include "extern.h"
  53
  54 #define LHSZ    128
  55 #define LHMASK  (LHSZ - 1)
  56 static struct labhash {
  57         struct  labhash *lh_next;
  58         uint_t  lh_hash;
  59         struct  s_command *lh_cmd;
  60         int     lh_ref;
  61 } *labels[LHSZ];
  62
  63 static char      *compile_addr(char *, struct s_addr *);
  64 static char      *compile_ccl(char **, char *);
  65 static char      *compile_delimited(char *, char *, int);
  66 static char      *compile_flags(char *, struct s_subst *);
  67 static regex_t   *compile_re(char *, int);
  68 static char      *compile_subst(char *, struct s_subst *);
  69 static char      *compile_text(void);
  70 static char      *compile_tr(char *, struct s_tr **);
  71 static struct s_command
  72                 **compile_stream(struct s_command **);
  73 static char      *duptoeol(char *, const char *);
  74 static void       enterlabel(struct s_command *);
  75 static struct s_command
  76                  *findlabel(char *);
  77 static void       fixuplabel(struct s_command *, struct s_command *);
  78 static void       uselabel(void);
  79
  80 /*
  81  * Command specification.  This is used to drive the command parser.
  82  */
  83 struct s_format {
  84         char code;                              /* Command code */
  85         int naddr;                              /* Number of address args */
  86         enum e_args args;                       /* Argument type */
  87 };
  88
  89 static struct s_format cmd_fmts[] = {
  90         {'{', 2, GROUP},
  91         {'}', 0, ENDGROUP},
  92         {'a', 1, TEXT},
  93         {'b', 2, BRANCH},
  94         {'c', 2, TEXT},
  95         {'d', 2, EMPTY},
  96         {'D', 2, EMPTY},
  97         {'g', 2, EMPTY},
  98         {'G', 2, EMPTY},
  99         {'h', 2, EMPTY},
 100         {'H', 2, EMPTY},
 101         {'i', 1, TEXT},
 102         {'l', 2, EMPTY},
 103         {'n', 2, EMPTY},
 104         {'N', 2, EMPTY},
 105         {'p', 2, EMPTY},
 106         {'P', 2, EMPTY},
 107         {'q', 1, EMPTY},
 108         {'r', 1, RFILE},
 109         {'s', 2, SUBST},
 110         {'t', 2, BRANCH},
 111         {'w', 2, WFILE},
 112         {'x', 2, EMPTY},
 113         {'y', 2, TR},
 114         {'!', 2, NONSEL},
 115         {':', 0, LABEL},
 116         {'#', 0, COMMENT},
 117         {'=', 1, EMPTY},
 118         {'\0', 0, COMMENT},
 119 };
 120
 121 /* The compiled program. */
 122 struct s_command *prog;
 123
 124 /*
 125  * Compile the program into prog.
 126  * Initialise appends.
 127  */
 128 void
 129 compile(void)
 130 {
 131         *compile_stream(&prog) = NULL;
 132         fixuplabel(prog, NULL);
 133         uselabel();
 134         if (appendnum == 0)
 135                 appends = NULL;
 136         else if ((appends = malloc(sizeof (struct s_appends) * appendnum)) ==
 137             NULL)
 138                 err(1, "malloc");
 139         if ((match = malloc((maxnsub + 1) * sizeof (regmatch_t))) == NULL)
 140                 err(1, "malloc");
 141 }
 142
 143 #define EATSPACE() do {                                                 \
 144         if (p)                                                          \
 145                 while (*p && isspace((unsigned char)*p))                \
 146                         p++;                                            \
 147         _NOTE(CONSTCOND)                                                \
 148 } while (0)
 149
 150 static struct s_command **
 151 compile_stream(struct s_command **link)
 152 {
 153         char *p;
 154         static char lbuf[_POSIX2_LINE_MAX + 1]; /* To save stack */
 155         struct s_command *cmd, *cmd2, *stack;
 156         struct s_format *fp;
 157         char re[_POSIX2_LINE_MAX + 1];
 158         int naddr;                              /* Number of addresses */
 159
 160         stack = 0;
 161         for (;;) {
 162                 if ((p = cu_fgets(lbuf, sizeof (lbuf), NULL)) == NULL) {
 163                         if (stack != 0)
 164                                 fatal(_("unexpected EOF (pending }'s)"));
 165                         return (link);
 166                 }
 167
 168 semicolon:      EATSPACE();
 169                 if (p) {
 170                         if (*p == '#' || *p == '\0')
 171                                 continue;
 172                         else if (*p == ';') {
 173                                 p++;
 174                                 goto semicolon;
 175                         }
 176                 }
 177                 if ((*link = cmd = malloc(sizeof (struct s_command))) == NULL)
 178                         err(1, "malloc");
 179                 link = &cmd->next;
 180                 cmd->startline = cmd->nonsel = 0;
 181                 /* First parse the addresses */
 182                 naddr = 0;
 183
 184 /* Valid characters to start an address */
 185 #define addrchar(c)     (strchr("0123456789/\\$", (c)))
 186                 if (addrchar(*p)) {
 187                         naddr++;
 188                         if ((cmd->a1 = malloc(sizeof (struct s_addr))) == NULL)
 189                                 err(1, "malloc");
 190                         p = compile_addr(p, cmd->a1);
 191                         EATSPACE();                             /* EXTENSION */
 192                         if (*p == ',') {
 193                                 p++;
 194                                 EATSPACE();                     /* EXTENSION */
 195                                 naddr++;
 196                                 if ((cmd->a2 = malloc(sizeof (struct s_addr)))
 197                                     == NULL)
 198                                         err(1, "malloc");
 199                                 p = compile_addr(p, cmd->a2);
 200                                 EATSPACE();
 201                         } else
 202                                 cmd->a2 = 0;
 203                 } else
 204                         cmd->a1 = cmd->a2 = 0;
 205
 206 nonsel:         /* Now parse the command */
 207                 if (!*p)
 208                         fatal(_("command expected"));
 209                 cmd->code = *p;
 210                 for (fp = cmd_fmts; fp->code; fp++)
 211                         if (fp->code == *p)
 212                                 break;
 213                 if (!fp->code)
 214                         fatal(_("invalid command code %c"), *p);
 215                 if (naddr > fp->naddr)
 216                         fatal(_("command %c expects up to %d address(es), "
 217                             "found %d"), *p, fp->naddr, naddr);
 218                 switch (fp->args) {
 219                 case NONSEL:                    /* ! */
 220                         p++;
 221                         EATSPACE();
 222                         cmd->nonsel = 1;
 223                         goto nonsel;
 224                 case GROUP:                     /* { */
 225                         p++;
 226                         EATSPACE();
 227                         cmd->next = stack;
 228                         stack = cmd;
 229                         link = &cmd->u.c;
 230                         if (*p)
 231                                 goto semicolon;
 232                         break;
 233                 case ENDGROUP:
 234                         /*
 235                          * Short-circuit command processing, since end of
 236                          * group is really just a noop.
 237                          */
 238                         cmd->nonsel = 1;
 239                         if (stack == 0)
 240                                 fatal(_("unexpected }"));
 241                         cmd2 = stack;
 242                         stack = cmd2->next;
 243                         cmd2->next = cmd;
 244                         /*FALLTHROUGH*/
 245                 case EMPTY:             /* d D g G h H l n N p P q x = \0 */
 246                         p++;
 247                         EATSPACE();
 248                         if (*p == ';') {
 249                                 p++;
 250                                 link = &cmd->next;
 251                                 goto semicolon;
 252                         }
 253                         if (*p)
 254                                 fatal(_("extra characters at the end of %c "
 255                                     "command"), cmd->code);
 256                         break;
 257                 case TEXT:                      /* a c i */
 258                         p++;
 259                         EATSPACE();
 260                         if (*p != '\\')
 261                                 fatal(_("command %c expects \\ "
 262                                     "followed by text"), cmd->code);
 263                         p++;
 264                         EATSPACE();
 265                         if (*p)
 266                                 fatal(_("extra characters after \\ "
 267                                     "at the end of %c command"),
 268                                     cmd->code);
 269                         cmd->t = compile_text();
 270                         break;
 271                 case COMMENT:                   /* \0 # */
 272                         break;
 273                 case WFILE:                     /* w */
 274                         p++;
 275                         EATSPACE();
 276                         if (*p == '\0')
 277                                 fatal(_("filename expected"));
 278                         cmd->t = duptoeol(p, "w command");
 279                         if (aflag)
 280                                 cmd->u.fd = -1;
 281                         else if ((cmd->u.fd = open(p,
 282                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC, 0666)) == -1)
 283                                 err(1, "%s", p);
 284                         break;
 285                 case RFILE:                     /* r */
 286                         p++;
 287                         EATSPACE();
 288                         if (*p == '\0')
 289                                 fatal(_("filename expected"));
 290                         else
 291                                 cmd->t = duptoeol(p, "read command");
 292                         break;
 293                 case BRANCH:                    /* b t */
 294                         p++;
 295                         EATSPACE();
 296                         if (*p == '\0')
 297                                 cmd->t = NULL;
 298                         else
 299                                 cmd->t = duptoeol(p, "branch");
 300                         break;
 301                 case LABEL:                     /* : */
 302                         p++;
 303                         EATSPACE();
 304                         cmd->t = duptoeol(p, "label");
 305                         if (strlen(p) == 0)
 306                                 fatal(_("empty label"));
 307                         enterlabel(cmd);
 308                         break;
 309                 case SUBST:                     /* s */
 310                         p++;
 311                         if (*p == '\0' || *p == '\\')
 312                                 fatal(_("substitute pattern can not "
 313                                     "be delimited by newline or backslash"));
 314                         if ((cmd->u.s = calloc(1, sizeof (struct s_subst))) ==
 315                             NULL)
 316                                 err(1, "malloc");
 317                         p = compile_delimited(p, re, 0);
 318                         if (p == NULL)
 319                                 fatal(_("unterminated substitute pattern"));
 320
 321                         /* Compile RE with no case sensitivity temporarily */
 322                         if (*re == '\0')
 323                                 cmd->u.s->re = NULL;
 324                         else
 325                                 cmd->u.s->re = compile_re(re, 0);
 326                         --p;
 327                         p = compile_subst(p, cmd->u.s);
 328                         p = compile_flags(p, cmd->u.s);
 329
 330                         /* Recompile RE with case sens. from "I" flag if any */
 331                         if (*re == '\0')
 332                                 cmd->u.s->re = NULL;
 333                         else
 334                                 cmd->u.s->re = compile_re(re, cmd->u.s->icase);
 335                         EATSPACE();
 336                         if (*p == ';') {
 337                                 p++;
 338                                 link = &cmd->next;
 339                                 goto semicolon;
 340                         }
 341                         break;
 342                 case TR:                        /* y */
 343                         p++;
 344                         p = compile_tr(p, &cmd->u.y);
 345                         EATSPACE();
 346                         if (*p == ';') {
 347                                 p++;
 348                                 link = &cmd->next;
 349                                 goto semicolon;
 350                         }
 351                         if (*p)
 352                                 fatal(_("extra text at the end of a "
 353                                     "transform command"));
 354                         break;
 355                 }
 356         }
 357 }
 358
 359 /*
 360  * Get a delimited string.  P points to the delimeter of the string; d points
 361  * to a buffer area.  Newline and delimiter escapes are processed; other
 362  * escapes are ignored.
 363  *
 364  * Returns a pointer to the first character after the final delimiter or NULL
 365  * in the case of a non-terminated string.  The character array d is filled
 366  * with the processed string.
 367  */
 368 static char *
 369 compile_delimited(char *p, char *d, int is_tr)
 370 {
 371         char c;
 372
 373         c = *p++;
 374         if (c == '\0')
 375                 return (NULL);
 376         else if (c == '\\')
 377                 fatal(_("\\ can not be used as a string delimiter"));
 378         else if (c == '\n')
 379                 fatal(_("newline can not be used as a string delimiter"));
 380         while (*p) {
 381                 if (*p == '[' && *p != c) {
 382                         if ((d = compile_ccl(&p, d)) == NULL)
 383                                 fatal(_("unbalanced brackets ([])"));
 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                         if (is_tr)
 395                                 p++;
 396                         else
 397                                 *d++ = *p++;
 398                 } else if (*p == c) {
 399                         *d = '\0';
 400                         return (p + 1);
 401                 }
 402                 *d++ = *p++;
 403         }
 404         return (NULL);
 405 }
 406
 407
 408 /* compile_ccl: expand a POSIX character class */
 409 static char *
 410 compile_ccl(char **sp, char *t)
 411 {
 412         int c, d;
 413         char *s = *sp;
 414
 415         *t++ = *s++;
 416         if (*s == '^')
 417                 *t++ = *s++;
 418         if (*s == ']')
 419                 *t++ = *s++;
 420         for (; *s && (*t = *s) != ']'; s++, t++)
 421                 if (*s == '[' &&
 422                     ((d = *(s+1)) == '.' || d == ':' || d == '=')) {
 423                         *++t = *++s, t++, s++;
 424                         for (c = *s; (*t = *s) != ']' || c != d; s++, t++)
 425                                 if ((c = *s) == '\0')
 426                                         return (NULL);
 427                 }
 428         return ((*s == ']') ? *sp = ++s, ++t : NULL);
 429 }
 430
 431 /*
 432  * Compiles the regular expression in RE and returns a pointer to the compiled
 433  * regular expression.
 434  * Cflags are passed to regcomp.
 435  */
 436 static regex_t *
 437 compile_re(char *re, int case_insensitive)
 438 {
 439         regex_t *rep;
 440         int eval, flags;
 441
 442
 443         flags = rflags;
 444         if (case_insensitive)
 445                 flags |= REG_ICASE;
 446         if ((rep = malloc(sizeof (regex_t))) == NULL)
 447                 err(1, "malloc");
 448         if ((eval = regcomp(rep, re, flags)) != 0)
 449                 fatal(_("RE error: %s"), strregerror(eval, rep));
 450         if (maxnsub < rep->re_nsub)
 451                 maxnsub = rep->re_nsub;
 452         return (rep);
 453 }
 454
 455 /*
 456  * Compile the substitution string of a regular expression and set res to
 457  * point to a saved copy of it.  Nsub is the number of parenthesized regular
 458  * expressions.
 459  */
 460 static char *
 461 compile_subst(char *p, struct s_subst *s)
 462 {
 463         static char lbuf[_POSIX2_LINE_MAX + 1];
 464         int asize;
 465         uintptr_t size;
 466         uchar_t ref;
 467         char c, *text, *op, *sp;
 468         int more = 1, sawesc = 0;
 469
 470         c = *p++;                       /* Terminator character */
 471         if (c == '\0')
 472                 return (NULL);
 473
 474         s->maxbref = 0;
 475         s->linenum = linenum;
 476         asize = 2 * _POSIX2_LINE_MAX + 1;
 477         if ((text = malloc(asize)) == NULL)
 478                 err(1, "malloc");
 479         size = 0;
 480         do {
 481                 op = sp = text + size;
 482                 for (; *p; p++) {
 483                         if (*p == '\\' || sawesc) {
 484                                 /*
 485                                  * If this is a continuation from the last
 486                                  * buffer, we won't have a character to
 487                                  * skip over.
 488                                  */
 489                                 if (sawesc)
 490                                         sawesc = 0;
 491                                 else
 492                                         p++;
 493
 494                                 if (*p == '\0') {
 495                                         /*
 496                                          * This escaped character is continued
 497                                          * in the next part of the line.  Note
 498                                          * this fact, then cause the loop to
 499                                          * exit w/ normal EOL case and reenter
 500                                          * above with the new buffer.
 501                                          */
 502                                         sawesc = 1;
 503                                         p--;
 504                                         continue;
 505                                 } else if (strchr("123456789", *p) != NULL) {
 506                                         *sp++ = '\\';
 507                                         ref = *p - '0';
 508                                         if (s->re != NULL &&
 509                                             ref > s->re->re_nsub)
 510                                                 fatal(_("not defined in "
 511                                                     "the RE: \\%c"), *p);
 512                                         if (s->maxbref < ref)
 513                                                 s->maxbref = ref;
 514                                 } else if (*p == '&' || *p == '\\')
 515                                         *sp++ = '\\';
 516                         } else if (*p == c) {
 517                                 if (*++p == '\0' && more) {
 518                                         if (cu_fgets(lbuf, sizeof (lbuf),
 519                                             &more))
 520                                                 p = lbuf;
 521                                 }
 522                                 *sp++ = '\0';
 523                                 size += (uintptr_t)sp - (uintptr_t)op;
 524                                 if ((s->new = realloc(text, size)) == NULL)
 525                                         err(1, "realloc");
 526                                 return (p);
 527                         } else if (*p == '\n') {
 528                                 fatal(_("unescaped newline inside "
 529                                     "substitute pattern"));
 530                                 /* NOTREACHED */
 531                         }
 532                         *sp++ = *p;
 533                 }
 534                 size += (uintptr_t)sp - (uintptr_t)op;
 535                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 536                         asize *= 2;
 537                         if ((text = realloc(text, asize)) == NULL)
 538                                 err(1, "realloc");
 539                 }
 540         } while (cu_fgets(p = lbuf, sizeof (lbuf), &more));
 541         fatal(_("unterminated substitute in regular expression"));
 542         return (NULL);
 543 }
 544
 545 /*
 546  * Compile the flags of the s command
 547  */
 548 static char *
 549 compile_flags(char *p, struct s_subst *s)
 550 {
 551         int gn;                 /* True if we have seen g or n */
 552         unsigned long nval;
 553         char wfile[_POSIX2_LINE_MAX + 1], *q;
 554
 555         s->n = 1;                               /* Default */
 556         s->p = 0;
 557         s->wfile = NULL;
 558         s->wfd = -1;
 559         s->icase = 0;
 560         gn = 0;
 561         for (;;) {
 562                 EATSPACE();                     /* EXTENSION */
 563                 switch (*p) {
 564                 case 'g':
 565                         if (gn)
 566                                 fatal(_("more than one number or "
 567                                     "'g' in substitute flags"));
 568                         gn = 1;
 569                         s->n = 0;
 570                         break;
 571                 case '\0':
 572                 case '\n':
 573                 case ';':
 574                         return (p);
 575                 case 'p':
 576                         s->p = 1;
 577                         break;
 578                 case 'I':
 579                         s->icase = 1;
 580                         break;
 581                 case '1': case '2': case '3':
 582                 case '4': case '5': case '6':
 583                 case '7': case '8': case '9':
 584                         if (gn)
 585                                 fatal(_("more than one number or "
 586                                     "'g' in substitute flags"));
 587                         gn = 1;
 588                         errno = 0;
 589                         nval = strtol(p, &p, 10);
 590                         if (errno == ERANGE || nval > INT_MAX)
 591                                 fatal(_("overflow in the 'N' substitute flag"));
 592                         s->n = nval;
 593                         p--;
 594                         break;
 595                 case 'w':
 596                         p++;
 597 #ifdef HISTORIC_PRACTICE
 598                         if (*p != ' ') {
 599                                 fatal(_("space missing before w wfile"));
 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                                 fatal(_("no wfile specified"));
 613                         s->wfile = strdup(wfile);
 614                         if (!aflag && (s->wfd = open(wfile,
 615                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC, 0666)) == -1)
 616                                 err(1, "%s", wfile);
 617                         return (p);
 618                 default:
 619                         fatal(_("bad flag in substitute command: '%c'"), *p);
 620                         break;
 621                 }
 622                 p++;
 623         }
 624 }
 625
 626 /*
 627  * Compile a translation set of strings into a lookup table.
 628  */
 629 static char *
 630 compile_tr(char *p, struct s_tr **py)
 631 {
 632         struct s_tr *y;
 633         int i;
 634         const char *op, *np;
 635         char old[_POSIX2_LINE_MAX + 1];
 636         char new[_POSIX2_LINE_MAX + 1];
 637         size_t oclen, oldlen, nclen, newlen;
 638         mbstate_t mbs1, mbs2;
 639
 640         if ((*py = y = malloc(sizeof (*y))) == NULL)
 641                 err(1, NULL);
 642         y->multis = NULL;
 643         y->nmultis = 0;
 644
 645         if (*p == '\0' || *p == '\\')
 646                 fatal(_("transform pattern can not be delimited by "
 647                     "newline or backslash"));
 648         p = compile_delimited(p, old, 1);
 649         if (p == NULL)
 650                 fatal(_("unterminated transform source string"));
 651         p = compile_delimited(p - 1, new, 1);
 652         if (p == NULL)
 653                 fatal(_("unterminated transform target string"));
 654         EATSPACE();
 655         op = old;
 656         oldlen = mbsrtowcs(NULL, &op, 0, NULL);
 657         if (oldlen == (size_t)-1)
 658                 err(1, NULL);
 659         np = new;
 660         newlen = mbsrtowcs(NULL, &np, 0, NULL);
 661         if (newlen == (size_t)-1)
 662                 err(1, NULL);
 663         if (newlen != oldlen)
 664                 fatal(_("transform strings are not the same length"));
 665         if (MB_CUR_MAX == 1) {
 666                 /*
 667                  * The single-byte encoding case is easy: generate a
 668                  * lookup table.
 669                  */
 670                 for (i = 0; i <= UCHAR_MAX; i++)
 671                         y->bytetab[i] = (char)i;
 672                 for (; *op; op++, np++)
 673                         y->bytetab[(uchar_t)*op] = *np;
 674         } else {
 675                 /*
 676                  * Multi-byte encoding case: generate a lookup table as
 677                  * above, but only for single-byte characters. The first
 678                  * bytes of multi-byte characters have their lookup table
 679                  * entries set to 0, which causes do_tr() to search through
 680                  * an auxiliary vector of multi-byte mappings.
 681                  */
 682                 (void) memset(&mbs1, 0, sizeof (mbs1));
 683                 (void) memset(&mbs2, 0, sizeof (mbs2));
 684                 for (i = 0; i <= UCHAR_MAX; i++)
 685                         y->bytetab[i] = (btowc(i) != WEOF) ? (uchar_t)i : 0;
 686                 while (*op != '\0') {
 687                         oclen = mbrlen(op, MB_LEN_MAX, &mbs1);
 688                         if (oclen == (size_t)-1 || oclen == (size_t)-2)
 689                                 errx(1, "%s", strerror(EILSEQ));
 690                         nclen = mbrlen(np, MB_LEN_MAX, &mbs2);
 691                         if (nclen == (size_t)-1 || nclen == (size_t)-2)
 692                                 errx(1, "%s", strerror(EILSEQ));
 693                         if (oclen == 1 && nclen == 1)
 694                                 y->bytetab[(uchar_t)*op] = *np;
 695                         else {
 696                                 y->bytetab[(uchar_t)*op] = 0;
 697                                 y->multis = realloc(y->multis,
 698                                     (y->nmultis + 1) * sizeof (*y->multis));
 699                                 if (y->multis == NULL)
 700                                         err(1, NULL);
 701                                 i = y->nmultis++;
 702                                 y->multis[i].fromlen = oclen;
 703                                 (void) memcpy(y->multis[i].from, op, oclen);
 704                                 y->multis[i].tolen = nclen;
 705                                 (void) memcpy(y->multis[i].to, np, nclen);
 706                         }
 707                         op += oclen;
 708                         np += nclen;
 709                 }
 710         }
 711         return (p);
 712 }
 713
 714 /*
 715  * Compile the text following an a or i command.
 716  */
 717 static char *
 718 compile_text(void)
 719 {
 720         int esc_nl;
 721         uintptr_t size, asize;
 722         char *text, *p, *op, *s;
 723         char lbuf[_POSIX2_LINE_MAX + 1];
 724
 725         asize = 2 * _POSIX2_LINE_MAX + 1;
 726         if ((text = malloc(asize)) == NULL)
 727                 err(1, "malloc");
 728         size = 0;
 729         while (cu_fgets(lbuf, sizeof (lbuf), NULL)) {
 730                 op = s = text + size;
 731                 p = lbuf;
 732                 EATSPACE();
 733                 for (esc_nl = 0; *p != '\0'; p++) {
 734                         if (*p == '\\' && p[1] != '\0' && *++p == '\n')
 735                                 esc_nl = 1;
 736                         *s++ = *p;
 737                 }
 738                 size += (uintptr_t)s - (uintptr_t)op;
 739                 if (!esc_nl) {
 740                         *s = '\0';
 741                         break;
 742                 }
 743                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 744                         asize *= 2;
 745                         if ((text = realloc(text, asize)) == NULL)
 746                                 err(1, "realloc");
 747                 }
 748         }
 749         text[size] = '\0';
 750         if ((p = realloc(text, size + 1)) == NULL)
 751                 err(1, "realloc");
 752         return (p);
 753 }
 754
 755 /*
 756  * Get an address and return a pointer to the first character after
 757  * it.  Fill the structure pointed to according to the address.
 758  */
 759 static char *
 760 compile_addr(char *p, struct s_addr *a)
 761 {
 762         char *end, re[_POSIX2_LINE_MAX + 1];
 763         int icase;
 764
 765         icase = 0;
 766
 767         a->type = 0;
 768         switch (*p) {
 769         case '\\':                              /* Context address */
 770                 ++p;
 771                 /* FALLTHROUGH */
 772         case '/':                               /* Context address */
 773                 p = compile_delimited(p, re, 0);
 774                 if (p == NULL)
 775                         fatal(_("unterminated regular expression"));
 776
 777                 /* Check for case insensitive regexp flag */
 778                 if (*p == 'I') {
 779                         icase = 1;
 780                         p++;
 781                 }
 782                 if (*re == '\0')
 783                         a->u.r = NULL;
 784                 else
 785                         a->u.r = compile_re(re, icase);
 786                 a->type = AT_RE;
 787                 return (p);
 788
 789         case '$':                               /* Last line */
 790                 a->type = AT_LAST;
 791                 return (p + 1);
 792
 793         case '+':                               /* Relative line number */
 794                 a->type = AT_RELLINE;
 795                 p++;
 796                 /* FALLTHROUGH */
 797                                                 /* Line number */
 798         case '0': case '1': case '2': case '3': case '4':
 799         case '5': case '6': case '7': case '8': case '9':
 800                 if (a->type == 0)
 801                         a->type = AT_LINE;
 802                 a->u.l = strtol(p, &end, 10);
 803                 return (end);
 804         default:
 805                 fatal(_("expected context address"));
 806                 return (NULL);
 807         }
 808 }
 809
 810 /*
 811  * duptoeol --
 812  *      Return a copy of all the characters up to \n or \0.
 813  */
 814 static char *
 815 duptoeol(char *s, const char *ctype)
 816 {
 817         size_t len;
 818         int ws;
 819         char *p, *start;
 820
 821         ws = 0;
 822         for (start = s; *s != '\0' && *s != '\n'; ++s)
 823                 ws = isspace((unsigned char)*s);
 824         *s = '\0';
 825         if (ws)
 826                 warnx(_("%lu: %s: whitespace after %s"), linenum, fname, ctype);
 827         len = (uintptr_t)s - (uintptr_t)start + 1;
 828         if ((p = malloc(len)) == NULL)
 829                 err(1, "malloc");
 830         return (memmove(p, start, len));
 831 }
 832
 833 /*
 834  * Convert goto label names to addresses, and count a and r commands, in
 835  * the given subset of the script.  Free the memory used by labels in b
 836  * and t commands (but not by :).
 837  *
 838  * TODO: Remove } nodes
 839  */
 840 static void
 841 fixuplabel(struct s_command *cp, struct s_command *end)
 842 {
 843
 844         for (; cp != end; cp = cp->next)
 845                 switch (cp->code) {
 846                 case 'a':
 847                 case 'r':
 848                         appendnum++;
 849                         break;
 850                 case 'b':
 851                 case 't':
 852                         /* Resolve branch target. */
 853                         if (cp->t == NULL) {
 854                                 cp->u.c = NULL;
 855                                 break;
 856                         }
 857                         if ((cp->u.c = findlabel(cp->t)) == NULL)
 858                                 fatal(_("undefined label '%s'"), cp->t);
 859                         free(cp->t);
 860                         break;
 861                 case '{':
 862                         /* Do interior commands. */
 863                         fixuplabel(cp->u.c, cp->next);
 864                         break;
 865                 }
 866 }
 867
 868 /*
 869  * Associate the given command label for later lookup.
 870  */
 871 static void
 872 enterlabel(struct s_command *cp)
 873 {
 874         struct labhash **lhp, *lh;
 875         uchar_t *p;
 876         uint_t h, c;
 877
 878         for (h = 0, p = (uchar_t *)cp->t; (c = *p) != 0; p++)
 879                 h = (h << 5) + h + c;
 880         lhp = &labels[h & LHMASK];
 881         for (lh = *lhp; lh != NULL; lh = lh->lh_next)
 882                 if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
 883                         fatal(_("duplicate label '%s'"), cp->t);
 884         if ((lh = malloc(sizeof (*lh))) == NULL)
 885                 err(1, "malloc");
 886         lh->lh_next = *lhp;
 887         lh->lh_hash = h;
 888         lh->lh_cmd = cp;
 889         lh->lh_ref = 0;
 890         *lhp = lh;
 891 }
 892
 893 /*
 894  * Find the label contained in the command l in the command linked
 895  * list cp.  L is excluded from the search.  Return NULL if not found.
 896  */
 897 static struct s_command *
 898 findlabel(char *name)
 899 {
 900         struct labhash *lh;
 901         uchar_t *p;
 902         uint_t h, c;
 903
 904         for (h = 0, p = (uchar_t *)name; (c = *p) != 0; p++)
 905                 h = (h << 5) + h + c;
 906         for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
 907                 if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
 908                         lh->lh_ref = 1;
 909                         return (lh->lh_cmd);
 910                 }
 911         }
 912         return (NULL);
 913 }
 914
 915 /*
 916  * Warn about any unused labels.  As a side effect, release the label hash
 917  * table space.
 918  */
 919 static void
 920 uselabel(void)
 921 {
 922         struct labhash *lh, *next;
 923         int i;
 924
 925         for (i = 0; i < LHSZ; i++) {
 926                 for (lh = labels[i]; lh != NULL; lh = next) {
 927                         next = lh->lh_next;
 928                         if (!lh->lh_ref)
 929                                 warnx(_("%lu: %s: unused label '%s'"),
 930                                     linenum, fname, lh->lh_cmd->t);
 931                         free(lh);
 932                 }
 933         }
 934 }