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