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 #ifndef lint
  39 static char sccsid[] = "@(#)compile.c   8.1 (Berkeley) 6/6/93";
  40 #endif /* not lint */
  41
  42 #include <sys/types.h>
  43 #include <sys/stat.h>
  44
  45 #include <ctype.h>
  46 #include <errno.h>
  47 #include <fcntl.h>
  48 #include <limits.h>
  49 #include <regex.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53
  54 #include "defs.h"
  55 #include "extern.h"
  56
  57 #define LHSZ    128
  58 #define LHMASK  (LHSZ - 1)
  59 static struct labhash {
  60         struct  labhash *lh_next;
  61         u_int   lh_hash;
  62         struct  s_command *lh_cmd;
  63         int     lh_ref;
  64 } *labels[LHSZ];
  65
  66 static char      *compile_addr __P((char *, struct s_addr *));
  67 static char      *compile_delimited __P((char *, char *));
  68 static char      *compile_flags __P((char *, struct s_subst *));
  69 static char      *compile_re __P((char *, regex_t **));
  70 static char      *compile_subst __P((char *, struct s_subst *));
  71 static char      *compile_text __P((void));
  72 static char      *compile_tr __P((char *, char **));
  73 static struct s_command
  74                 **compile_stream __P((char *, struct s_command **, char *));
  75 static char      *duptoeol __P((char *, char *));
  76 static void       enterlabel __P((struct s_command *));
  77 static struct s_command
  78                  *findlabel __P((char *));
  79 static void       fixuplabel __P((struct s_command *, struct s_command *));
  80 static void       uselabel __P((void));
  81
  82 /*
  83  * Command specification.  This is used to drive the command parser.
  84  */
  85 struct s_format {
  86         char code;                              /* Command code */
  87         int naddr;                              /* Number of address args */
  88         enum e_args args;                       /* Argument type */
  89 };
  90
  91 static struct s_format cmd_fmts[] = {
  92         {'{', 2, GROUP},
  93         {'a', 1, TEXT},
  94         {'b', 2, BRANCH},
  95         {'c', 2, TEXT},
  96         {'d', 2, EMPTY},
  97         {'D', 2, EMPTY},
  98         {'g', 2, EMPTY},
  99         {'G', 2, EMPTY},
 100         {'h', 2, EMPTY},
 101         {'H', 2, EMPTY},
 102         {'i', 1, TEXT},
 103         {'l', 2, EMPTY},
 104         {'n', 2, EMPTY},
 105         {'N', 2, EMPTY},
 106         {'p', 2, EMPTY},
 107         {'P', 2, EMPTY},
 108         {'q', 1, EMPTY},
 109         {'r', 1, RFILE},
 110         {'s', 2, SUBST},
 111         {'t', 2, BRANCH},
 112         {'w', 2, WFILE},
 113         {'x', 2, EMPTY},
 114         {'y', 2, TR},
 115         {'!', 2, NONSEL},
 116         {':', 0, LABEL},
 117         {'#', 0, COMMENT},
 118         {'=', 1, EMPTY},
 119         {'\0', 0, COMMENT},
 120 };
 121
 122 /* The compiled program. */
 123 struct s_command *prog;
 124
 125 /*
 126  * Compile the program into prog.
 127  * Initialise appends.
 128  */
 129 void
 130 compile()
 131 {
 132         *compile_stream(NULL, &prog, NULL) = NULL;
 133         fixuplabel(prog, NULL);
 134         uselabel();
 135         appends = xmalloc(sizeof(struct s_appends) * appendnum);
 136         match = xmalloc((maxnsub + 1) * sizeof(regmatch_t));
 137 }
 138
 139 #define EATSPACE() do {                                                 \
 140         if (p)                                                          \
 141                 while (*p && isascii(*p) && isspace(*p))                \
 142                         p++;                                            \
 143         } while (0)
 144
 145 static struct s_command **
 146 compile_stream(terminator, link, p)
 147         char *terminator;
 148         struct s_command **link;
 149         register char *p;
 150 {
 151         static char lbuf[_POSIX2_LINE_MAX + 1]; /* To save stack */
 152         struct s_command *cmd, *cmd2;
 153         struct s_format *fp;
 154         int naddr;                              /* Number of addresses */
 155
 156         if (p != NULL)
 157                 goto semicolon;
 158         for (;;) {
 159                 if ((p = cu_fgets(lbuf, sizeof(lbuf))) == NULL) {
 160                         if (terminator != NULL)
 161                                 err(COMPILE, "unexpected EOF (pending }'s)");
 162                         return (link);
 163                 }
 164
 165 semicolon:      EATSPACE();
 166                 if (p && (*p == '#' || *p == '\0'))
 167                         continue;
 168                 if (*p == '}') {
 169                         if (terminator == NULL)
 170                                 err(COMPILE, "unexpected }");
 171                         return (link);
 172                 }
 173                 *link = cmd = xmalloc(sizeof(struct s_command));
 174                 link = &cmd->next;
 175                 cmd->nonsel = cmd->inrange = 0;
 176                 /* First parse the addresses */
 177                 naddr = 0;
 178                 cmd->a1 = cmd->a2 = NULL;
 179
 180 /* Valid characters to start an address */
 181 #define addrchar(c)     (strchr("0123456789/\\$", (c)))
 182                 if (addrchar(*p)) {
 183                         naddr++;
 184                         cmd->a1 = xmalloc(sizeof(struct s_addr));
 185                         p = compile_addr(p, cmd->a1);
 186                         EATSPACE();                             /* EXTENSION */
 187                         if (*p == ',') {
 188                                 naddr++;
 189                                 p++;
 190                                 EATSPACE();                     /* EXTENSION */
 191                                 cmd->a2 = xmalloc(sizeof(struct s_addr));
 192                                 p = compile_addr(p, cmd->a2);
 193                         }
 194                 }
 195
 196 nonsel:         /* Now parse the command */
 197                 EATSPACE();
 198                 if (!*p)
 199                         err(COMPILE, "command expected");
 200                 cmd->code = *p;
 201                 for (fp = cmd_fmts; fp->code; fp++)
 202                         if (fp->code == *p)
 203                                 break;
 204                 if (!fp->code)
 205                         err(COMPILE, "invalid command code %c", *p);
 206                 if (naddr > fp->naddr)
 207                         err(COMPILE,
 208 "command %c expects up to %d address(es), found %d", *p, fp->naddr, naddr);
 209                 switch (fp->args) {
 210                 case NONSEL:                    /* ! */
 211                         cmd->nonsel = ! cmd->nonsel;
 212                         p++;
 213                         goto nonsel;
 214                 case GROUP:                     /* { */
 215                         p++;
 216                         EATSPACE();
 217                         if (!*p)
 218                                 p = NULL;
 219                         cmd2 = xmalloc(sizeof(struct s_command));
 220                         cmd2->code = '}';
 221                         *compile_stream("}", &cmd->u.c, p) = cmd2;
 222                         cmd->next = cmd2;
 223                         link = &cmd2->next;
 224                         break;
 225                 case EMPTY:             /* d D g G h H l n N p P q x = \0 */
 226                         p++;
 227                         EATSPACE();
 228                         if (*p == ';') {
 229                                 p++;
 230                                 link = &cmd->next;
 231                                 goto semicolon;
 232                         }
 233                         if (*p)
 234                                 err(COMPILE,
 235 "extra characters at the end of %c command", cmd->code);
 236                         break;
 237                 case TEXT:                      /* a c i */
 238                         p++;
 239                         EATSPACE();
 240                         if (*p != '\\')
 241                                 err(COMPILE,
 242 "command %c expects \\ followed by text", cmd->code);
 243                         p++;
 244                         EATSPACE();
 245                         if (*p)
 246                                 err(COMPILE,
 247 "extra characters after \\ at the end of %c command", cmd->code);
 248                         cmd->t = compile_text();
 249                         break;
 250                 case COMMENT:                   /* \0 # */
 251                         break;
 252                 case WFILE:                     /* w */
 253                         p++;
 254                         EATSPACE();
 255                         if (*p == '\0')
 256                                 err(COMPILE, "filename expected");
 257                         cmd->t = duptoeol(p, "w command");
 258                         if (aflag)
 259                                 cmd->u.fd = -1;
 260                         else if ((cmd->u.fd = open(p,
 261                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 262                             DEFFILEMODE)) == -1)
 263                                 err(FATAL, "%s: %s\n", p, strerror(errno));
 264                         break;
 265                 case RFILE:                     /* r */
 266                         p++;
 267                         EATSPACE();
 268                         if (*p == '\0')
 269                                 err(COMPILE, "filename expected");
 270                         else
 271                                 cmd->t = duptoeol(p, "read command");
 272                         break;
 273                 case BRANCH:                    /* b t */
 274                         p++;
 275                         EATSPACE();
 276                         if (*p == '\0')
 277                                 cmd->t = NULL;
 278                         else
 279                                 cmd->t = duptoeol(p, "branch");
 280                         break;
 281                 case LABEL:                     /* : */
 282                         p++;
 283                         EATSPACE();
 284                         cmd->t = duptoeol(p, "label");
 285                         if (strlen(p) == 0)
 286                                 err(COMPILE, "empty label");
 287                         enterlabel(cmd);
 288                         break;
 289                 case SUBST:                     /* s */
 290                         p++;
 291                         if (*p == '\0' || *p == '\\')
 292                                 err(COMPILE,
 293 "substitute pattern can not be delimited by newline or backslash");
 294                         cmd->u.s = xmalloc(sizeof(struct s_subst));
 295                         p = compile_re(p, &cmd->u.s->re);
 296                         if (p == NULL)
 297                                 err(COMPILE, "unterminated substitute pattern");
 298                         --p;
 299                         p = compile_subst(p, cmd->u.s);
 300                         p = compile_flags(p, cmd->u.s);
 301                         EATSPACE();
 302                         if (*p == ';') {
 303                                 p++;
 304                                 link = &cmd->next;
 305                                 goto semicolon;
 306                         }
 307                         break;
 308                 case TR:                        /* y */
 309                         p++;
 310                         p = compile_tr(p, (char **)&cmd->u.y);
 311                         EATSPACE();
 312                         if (*p == ';') {
 313                                 p++;
 314                                 link = &cmd->next;
 315                                 goto semicolon;
 316                         }
 317                         if (*p)
 318                                 err(COMPILE,
 319 "extra text at the end of a transform command");
 320                         break;
 321                 }
 322         }
 323 }
 324
 325 /*
 326  * Get a delimited string.  P points to the delimeter of the string; d points
 327  * to a buffer area.  Newline and delimiter escapes are processed; other
 328  * escapes are ignored.
 329  *
 330  * Returns a pointer to the first character after the final delimiter or NULL
 331  * in the case of a non-terminated string.  The character array d is filled
 332  * with the processed string.
 333  */
 334 static char *
 335 compile_delimited(p, d)
 336         char *p, *d;
 337 {
 338         char c;
 339
 340         c = *p++;
 341         if (c == '\0')
 342                 return (NULL);
 343         else if (c == '\\')
 344                 err(COMPILE, "\\ can not be used as a string delimiter");
 345         else if (c == '\n')
 346                 err(COMPILE, "newline can not be used as a string delimiter");
 347         while (*p) {
 348                 if (*p == '\\' && p[1] == c)
 349                         p++;
 350                 else if (*p == '\\' && p[1] == 'n') {
 351                         *d++ = '\n';
 352                         p += 2;
 353                         continue;
 354                 } else if (*p == '\\' && p[1] == '\\')
 355                         *d++ = *p++;
 356                 else if (*p == c) {
 357                         *d = '\0';
 358                         return (p + 1);
 359                 }
 360                 *d++ = *p++;
 361         }
 362         return (NULL);
 363 }
 364
 365 /*
 366  * Get a regular expression.  P points to the delimiter of the regular
 367  * expression; repp points to the address of a regexp pointer.  Newline
 368  * and delimiter escapes are processed; other escapes are ignored.
 369  * Returns a pointer to the first character after the final delimiter
 370  * or NULL in the case of a non terminated regular expression.  The regexp
 371  * pointer is set to the compiled regular expression.
 372  * Cflags are passed to regcomp.
 373  */
 374 static char *
 375 compile_re(p, repp)
 376         char *p;
 377         regex_t **repp;
 378 {
 379         int eval;
 380         char re[_POSIX2_LINE_MAX + 1];
 381
 382         p = compile_delimited(p, re);
 383         if (p && strlen(re) == 0) {
 384                 *repp = NULL;
 385                 return (p);
 386         }
 387         *repp = xmalloc(sizeof(regex_t));
 388         if (p && (eval = regcomp(*repp, re, 0)) != 0)
 389                 err(COMPILE, "RE error: %s", strregerror(eval, *repp));
 390         if (maxnsub < (*repp)->re_nsub)
 391                 maxnsub = (*repp)->re_nsub;
 392         return (p);
 393 }
 394
 395 /*
 396  * Compile the substitution string of a regular expression and set res to
 397  * point to a saved copy of it.  Nsub is the number of parenthesized regular
 398  * expressions.
 399  */
 400 static char *
 401 compile_subst(p, s)
 402         char *p;
 403         struct s_subst *s;
 404 {
 405         static char lbuf[_POSIX2_LINE_MAX + 1];
 406         int asize, ref, size;
 407         char c, *text, *op, *sp;
 408
 409         c = *p++;                       /* Terminator character */
 410         if (c == '\0')
 411                 return (NULL);
 412
 413         s->maxbref = 0;
 414         s->linenum = linenum;
 415         asize = 2 * _POSIX2_LINE_MAX + 1;
 416         text = xmalloc(asize);
 417         size = 0;
 418         do {
 419                 op = sp = text + size;
 420                 for (; *p; p++) {
 421                         if (*p == '\\') {
 422                                 p++;
 423                                 if (strchr("123456789", *p) != NULL) {
 424                                         *sp++ = '\\';
 425                                         ref = *p - '0';
 426                                         if (s->re != NULL &&
 427                                             ref > s->re->re_nsub)
 428                                                 err(COMPILE,
 429 "\\%c not defined in the RE", *p);
 430                                         if (s->maxbref < ref)
 431                                                 s->maxbref = ref;
 432                                 } else if (*p == '&' || *p == '\\')
 433                                         *sp++ = '\\';
 434                         } else if (*p == c) {
 435                                 p++;
 436                                 *sp++ = '\0';
 437                                 size += sp - op;
 438                                 s->new = xrealloc(text, size);
 439                                 return (p);
 440                         } else if (*p == '\n') {
 441                                 err(COMPILE,
 442 "unescaped newline inside substitute pattern");
 443                                 /* NOTREACHED */
 444                         }
 445                         *sp++ = *p;
 446                 }
 447                 size += sp - op;
 448                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 449                         asize *= 2;
 450                         text = xmalloc(asize);
 451                 }
 452         } while (cu_fgets(p = lbuf, sizeof(lbuf)));
 453         err(COMPILE, "unterminated substitute in regular expression");
 454         /* NOTREACHED */
 455 }
 456
 457 /*
 458  * Compile the flags of the s command
 459  */
 460 static char *
 461 compile_flags(p, s)
 462         char *p;
 463         struct s_subst *s;
 464 {
 465         int gn;                 /* True if we have seen g or n */
 466         char wfile[_POSIX2_LINE_MAX + 1], *q;
 467
 468         s->n = 1;                               /* Default */
 469         s->p = 0;
 470         s->wfile = NULL;
 471         s->wfd = -1;
 472         for (gn = 0;;) {
 473                 EATSPACE();                     /* EXTENSION */
 474                 switch (*p) {
 475                 case 'g':
 476                         if (gn)
 477                                 err(COMPILE,
 478 "more than one number or 'g' in substitute flags");
 479                         gn = 1;
 480                         s->n = 0;
 481                         break;
 482                 case '\0':
 483                 case '\n':
 484                 case ';':
 485                         return (p);
 486                 case 'p':
 487                         s->p = 1;
 488                         break;
 489                 case '1': case '2': case '3':
 490                 case '4': case '5': case '6':
 491                 case '7': case '8': case '9':
 492                         if (gn)
 493                                 err(COMPILE,
 494 "more than one number or 'g' in substitute flags");
 495                         gn = 1;
 496                         /* XXX Check for overflow */
 497                         s->n = (int)strtol(p, &p, 10);
 498                         break;
 499                 case 'w':
 500                         p++;
 501 #ifdef HISTORIC_PRACTICE
 502                         if (*p != ' ') {
 503                                 err(WARNING, "space missing before w wfile");
 504                                 return (p);
 505                         }
 506 #endif
 507                         EATSPACE();
 508                         q = wfile;
 509                         while (*p) {
 510                                 if (*p == '\n')
 511                                         break;
 512                                 *q++ = *p++;
 513                         }
 514                         *q = '\0';
 515                         if (q == wfile)
 516                                 err(COMPILE, "no wfile specified");
 517                         s->wfile = strdup(wfile);
 518                         if (!aflag && (s->wfd = open(wfile,
 519                             O_WRONLY|O_APPEND|O_CREAT|O_TRUNC,
 520                             DEFFILEMODE)) == -1)
 521                                 err(FATAL, "%s: %s\n", wfile, strerror(errno));
 522                         return (p);
 523                 default:
 524                         err(COMPILE,
 525                             "bad flag in substitute command: '%c'", *p);
 526                         break;
 527                 }
 528                 p++;
 529         }
 530 }
 531
 532 /*
 533  * Compile a translation set of strings into a lookup table.
 534  */
 535 static char *
 536 compile_tr(p, transtab)
 537         char *p;
 538         char **transtab;
 539 {
 540         int i;
 541         char *lt, *op, *np;
 542         char old[_POSIX2_LINE_MAX + 1];
 543         char new[_POSIX2_LINE_MAX + 1];
 544
 545         if (*p == '\0' || *p == '\\')
 546                 err(COMPILE,
 547 "transform pattern can not be delimited by newline or backslash");
 548         p = compile_delimited(p, old);
 549         if (p == NULL) {
 550                 err(COMPILE, "unterminated transform source string");
 551                 return (NULL);
 552         }
 553         p = compile_delimited(--p, new);
 554         if (p == NULL) {
 555                 err(COMPILE, "unterminated transform target string");
 556                 return (NULL);
 557         }
 558         EATSPACE();
 559         if (strlen(new) != strlen(old)) {
 560                 err(COMPILE, "transform strings are not the same length");
 561                 return (NULL);
 562         }
 563         /* We assume characters are 8 bits */
 564         lt = xmalloc(UCHAR_MAX);
 565         for (i = 0; i <= UCHAR_MAX; i++)
 566                 lt[i] = (char)i;
 567         for (op = old, np = new; *op; op++, np++)
 568                 lt[(u_char)*op] = *np;
 569         *transtab = lt;
 570         return (p);
 571 }
 572
 573 /*
 574  * Compile the text following an a or i command.
 575  */
 576 static char *
 577 compile_text()
 578 {
 579         int asize, size;
 580         char *text, *p, *op, *s;
 581         char lbuf[_POSIX2_LINE_MAX + 1];
 582
 583         asize = 2 * _POSIX2_LINE_MAX + 1;
 584         text = xmalloc(asize);
 585         size = 0;
 586         while (cu_fgets(lbuf, sizeof(lbuf))) {
 587                 op = s = text + size;
 588                 p = lbuf;
 589                 EATSPACE();
 590                 for (; *p; p++) {
 591                         if (*p == '\\')
 592                                 p++;
 593                         *s++ = *p;
 594                 }
 595                 size += s - op;
 596                 if (p[-2] != '\\') {
 597                         *s = '\0';
 598                         break;
 599                 }
 600                 if (asize - size < _POSIX2_LINE_MAX + 1) {
 601                         asize *= 2;
 602                         text = xmalloc(asize);
 603                 }
 604         }
 605         return (xrealloc(text, size + 1));
 606 }
 607
 608 /*
 609  * Get an address and return a pointer to the first character after
 610  * it.  Fill the structure pointed to according to the address.
 611  */
 612 static char *
 613 compile_addr(p, a)
 614         char *p;
 615         struct s_addr *a;
 616 {
 617         char *end;
 618
 619         switch (*p) {
 620         case '\\':                              /* Context address */
 621                 ++p;
 622                 /* FALLTHROUGH */
 623         case '/':                               /* Context address */
 624                 p = compile_re(p, &a->u.r);
 625                 if (p == NULL)
 626                         err(COMPILE, "unterminated regular expression");
 627                 a->type = AT_RE;
 628                 return (p);
 629
 630         case '$':                               /* Last line */
 631                 a->type = AT_LAST;
 632                 return (p + 1);
 633                                                 /* Line number */
 634         case '0': case '1': case '2': case '3': case '4':
 635         case '5': case '6': case '7': case '8': case '9':
 636                 a->type = AT_LINE;
 637                 a->u.l = strtol(p, &end, 10);
 638                 return (end);
 639         default:
 640                 err(COMPILE, "expected context address");
 641                 return (NULL);
 642         }
 643 }
 644
 645 /*
 646  * duptoeol --
 647  *      Return a copy of all the characters up to \n or \0.
 648  */
 649 static char *
 650 duptoeol(s, ctype)
 651         register char *s;
 652         char *ctype;
 653 {
 654         size_t len;
 655         int ws;
 656         char *start;
 657
 658         ws = 0;
 659         for (start = s; *s != '\0' && *s != '\n'; ++s)
 660                 ws = isspace(*s);
 661         *s = '\0';
 662         if (ws)
 663                 err(WARNING, "whitespace after %s", ctype);
 664         len = s - start + 1;
 665         return (memmove(xmalloc(len), start, len));
 666 }
 667
 668 /*
 669  * Convert goto label names to addresses, and count a and r commands, in
 670  * the given subset of the script.  Free the memory used by labels in b
 671  * and t commands (but not by :).
 672  *
 673  * TODO: Remove } nodes
 674  */
 675 static void
 676 fixuplabel(cp, end)
 677         struct s_command *cp, *end;
 678 {
 679
 680         for (; cp != end; cp = cp->next)
 681                 switch (cp->code) {
 682                 case 'a':
 683                 case 'r':
 684                         appendnum++;
 685                         break;
 686                 case 'b':
 687                 case 't':
 688                         /* Resolve branch target. */
 689                         if (cp->t == NULL) {
 690                                 cp->u.c = NULL;
 691                                 break;
 692                         }
 693                         if ((cp->u.c = findlabel(cp->t)) == NULL)
 694                                 err(COMPILE2, "undefined label '%s'", cp->t);
 695                         free(cp->t);
 696                         break;
 697                 case '{':
 698                         /* Do interior commands. */
 699                         fixuplabel(cp->u.c, cp->next);
 700                         break;
 701                 }
 702 }
 703
 704 /*
 705  * Associate the given command label for later lookup.
 706  */
 707 static void
 708 enterlabel(cp)
 709         struct s_command *cp;
 710 {
 711         register struct labhash **lhp, *lh;
 712         register u_char *p;
 713         register u_int h, c;
 714
 715         for (h = 0, p = (u_char *)cp->t; (c = *p) != 0; p++)
 716                 h = (h << 5) + h + c;
 717         lhp = &labels[h & LHMASK];
 718         for (lh = *lhp; lh != NULL; lh = lh->lh_next)
 719                 if (lh->lh_hash == h && strcmp(cp->t, lh->lh_cmd->t) == 0)
 720                         err(COMPILE2, "duplicate label '%s'", cp->t);
 721         lh = xmalloc(sizeof *lh);
 722         lh->lh_next = *lhp;
 723         lh->lh_hash = h;
 724         lh->lh_cmd = cp;
 725         lh->lh_ref = 0;
 726         *lhp = lh;
 727 }
 728
 729 /*
 730  * Find the label contained in the command l in the command linked
 731  * list cp.  L is excluded from the search.  Return NULL if not found.
 732  */
 733 static struct s_command *
 734 findlabel(name)
 735         char *name;
 736 {
 737         register struct labhash *lh;
 738         register u_char *p;
 739         register u_int h, c;
 740
 741         for (h = 0, p = (u_char *)name; (c = *p) != 0; p++)
 742                 h = (h << 5) + h + c;
 743         for (lh = labels[h & LHMASK]; lh != NULL; lh = lh->lh_next) {
 744                 if (lh->lh_hash == h && strcmp(name, lh->lh_cmd->t) == 0) {
 745                         lh->lh_ref = 1;
 746                         return (lh->lh_cmd);
 747                 }
 748         }
 749         return (NULL);
 750 }
 751
 752 /*
 753  * Warn about any unused labels.  As a side effect, release the label hash
 754  * table space.
 755  */
 756 static void
 757 uselabel()
 758 {
 759         register struct labhash *lh, *next;
 760         register int i;
 761
 762         for (i = 0; i < LHSZ; i++) {
 763                 for (lh = labels[i]; lh != NULL; lh = next) {
 764                         next = lh->lh_next;
 765                         if (!lh->lh_ref)
 766                                 err(WARNING, "unused label '%s'",
 767                                     lh->lh_cmd->t);
 768                         free(lh);
 769                 }
 770         }
 771 }