1 /*- 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Kenneth Almquist. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)expand.c 8.3 (Berkeley) 04/28/95"; 13 #endif /* not lint */ 14 15 /* 16 * Routines to expand arguments to commands. We have to deal with 17 * backquotes, shell variables, and file metacharacters. 18 */ 19 20 #include "shell.h" 21 #include "main.h" 22 #include "nodes.h" 23 #include "eval.h" 24 #include "expand.h" 25 #include "syntax.h" 26 #include "parser.h" 27 #include "jobs.h" 28 #include "options.h" 29 #include "var.h" 30 #include "input.h" 31 #include "output.h" 32 #include "memalloc.h" 33 #include "error.h" 34 #include "mystring.h" 35 #include <sys/types.h> 36 #include <sys/time.h> 37 #include <sys/stat.h> 38 #include <errno.h> 39 #include <dirent.h> 40 #include <pwd.h> 41 42 /* 43 * Structure specifying which parts of the string should be searched 44 * for IFS characters. 45 */ 46 47 struct ifsregion { 48 struct ifsregion *next; /* next region in list */ 49 int begoff; /* offset of start of region */ 50 int endoff; /* offset of end of region */ 51 int nulonly; /* search for nul bytes only */ 52 }; 53 54 55 char *expdest; /* output of current string */ 56 struct nodelist *argbackq; /* list of back quote expressions */ 57 struct ifsregion ifsfirst; /* first struct in list of ifs regions */ 58 struct ifsregion *ifslastp; /* last struct in list */ 59 struct arglist exparg; /* holds expanded arg list */ 60 61 #ifdef __STDC__ 62 STATIC void argstr(char *, int); 63 STATIC void expbackq(union node *, int, int); 64 STATIC int subevalvar(char *, char *, int, int, int); 65 STATIC char *evalvar(char *, int); 66 STATIC int varisset(int); 67 STATIC void varvalue(int, int, int); 68 STATIC void recordregion(int, int, int); 69 STATIC void ifsbreakup(char *, struct arglist *); 70 STATIC void expandmeta(struct strlist *, int); 71 STATIC void expmeta(char *, char *); 72 STATIC void expari(int); 73 STATIC void addfname(char *); 74 STATIC struct strlist *expsort(struct strlist *); 75 STATIC struct strlist *msort(struct strlist *, int); 76 STATIC int pmatch(char *, char *); 77 STATIC char *exptilde(char *, int); 78 STATIC char *cvtnum(int, char *); 79 #else 80 STATIC void argstr(); 81 STATIC void expbackq(); 82 STATIC int subevalvar(); 83 STATIC char *evalvar(); 84 STATIC int varisset(); 85 STATIC void varvalue(); 86 STATIC void recordregion(); 87 STATIC void ifsbreakup(); 88 STATIC void expandmeta(); 89 STATIC void expmeta(); 90 STATIC void expari(); 91 STATIC void addfname(); 92 STATIC struct strlist *expsort(); 93 STATIC struct strlist *msort(); 94 STATIC int pmatch(); 95 STATIC char *exptilde(); 96 STATIC char *cvtnum(); 97 #endif 98 99 /* 100 * Expand shell variables and backquotes inside a here document. 101 */ 102 103 void 104 expandhere(arg, fd) 105 union node *arg; /* the document */ 106 int fd; /* where to write the expanded version */ 107 { 108 herefd = fd; 109 expandarg(arg, (struct arglist *)NULL, 0); 110 xwrite(fd, stackblock(), expdest - stackblock()); 111 } 112 113 114 /* 115 * Perform variable substitution and command substitution on an argument, 116 * placing the resulting list of arguments in arglist. If EXP_FULL is true, 117 * perform splitting and file name expansion. When arglist is NULL, perform 118 * here document expansion. 119 */ 120 121 void 122 expandarg(arg, arglist, flag) 123 union node *arg; 124 struct arglist *arglist; 125 { 126 struct strlist *sp; 127 char *p; 128 129 argbackq = arg->narg.backquote; 130 STARTSTACKSTR(expdest); 131 ifsfirst.next = NULL; 132 ifslastp = NULL; 133 argstr(arg->narg.text, flag); 134 if (arglist == NULL) { 135 return; /* here document expanded */ 136 } 137 STPUTC('\0', expdest); 138 p = grabstackstr(expdest); 139 exparg.lastp = &exparg.list; 140 /* 141 * TODO - EXP_REDIR 142 */ 143 if (flag & EXP_FULL) { 144 ifsbreakup(p, &exparg); 145 *exparg.lastp = NULL; 146 exparg.lastp = &exparg.list; 147 expandmeta(exparg.list, flag); 148 } else { 149 if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */ 150 rmescapes(p); 151 sp = (struct strlist *)stalloc(sizeof (struct strlist)); 152 sp->text = p; 153 *exparg.lastp = sp; 154 exparg.lastp = &sp->next; 155 } 156 while (ifsfirst.next != NULL) { 157 struct ifsregion *ifsp; 158 INTOFF; 159 ifsp = ifsfirst.next->next; 160 ckfree(ifsfirst.next); 161 ifsfirst.next = ifsp; 162 INTON; 163 } 164 *exparg.lastp = NULL; 165 if (exparg.list) { 166 *arglist->lastp = exparg.list; 167 arglist->lastp = exparg.lastp; 168 } 169 } 170 171 172 173 /* 174 * Perform variable and command substitution. If EXP_FULL is set, output CTLESC 175 * characters to allow for further processing. Otherwise treat 176 * $@ like $* since no splitting will be performed. 177 */ 178 179 STATIC void 180 argstr(p, flag) 181 register char *p; 182 { 183 register char c; 184 int quotes = flag & (EXP_FULL | EXP_CASE); /* do CTLESC */ 185 int firsteq = 1; 186 187 if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE))) 188 p = exptilde(p, flag); 189 for (;;) { 190 switch (c = *p++) { 191 case '\0': 192 case CTLENDVAR: /* ??? */ 193 goto breakloop; 194 case CTLESC: 195 if (quotes) 196 STPUTC(c, expdest); 197 c = *p++; 198 STPUTC(c, expdest); 199 break; 200 case CTLVAR: 201 p = evalvar(p, flag); 202 break; 203 case CTLBACKQ: 204 case CTLBACKQ|CTLQUOTE: 205 expbackq(argbackq->n, c & CTLQUOTE, flag); 206 argbackq = argbackq->next; 207 break; 208 case CTLENDARI: 209 expari(flag); 210 break; 211 case ':': 212 case '=': 213 /* 214 * sort of a hack - expand tildes in variable 215 * assignments (after the first '=' and after ':'s). 216 */ 217 STPUTC(c, expdest); 218 if (flag & EXP_VARTILDE && *p == '~') { 219 if (c == '=') { 220 if (firsteq) 221 firsteq = 0; 222 else 223 break; 224 } 225 p = exptilde(p, flag); 226 } 227 break; 228 default: 229 STPUTC(c, expdest); 230 } 231 } 232 breakloop:; 233 } 234 235 STATIC char * 236 exptilde(p, flag) 237 char *p; 238 { 239 char c, *startp = p; 240 struct passwd *pw; 241 char *home; 242 int quotes = flag & (EXP_FULL | EXP_CASE); 243 244 while (c = *p) { 245 switch(c) { 246 case CTLESC: 247 return (startp); 248 case ':': 249 if (flag & EXP_VARTILDE) 250 goto done; 251 break; 252 case '/': 253 goto done; 254 } 255 p++; 256 } 257 done: 258 *p = '\0'; 259 if (*(startp+1) == '\0') { 260 if ((home = lookupvar("HOME")) == NULL) 261 goto lose; 262 } else { 263 if ((pw = getpwnam(startp+1)) == NULL) 264 goto lose; 265 home = pw->pw_dir; 266 } 267 if (*home == '\0') 268 goto lose; 269 *p = c; 270 while (c = *home++) { 271 if (quotes && SQSYNTAX[c] == CCTL) 272 STPUTC(CTLESC, expdest); 273 STPUTC(c, expdest); 274 } 275 return (p); 276 lose: 277 *p = c; 278 return (startp); 279 } 280 281 282 /* 283 * Expand arithmetic expression. Backup to start of expression, 284 * evaluate, place result in (backed up) result, adjust string position. 285 */ 286 void 287 expari(flag) 288 { 289 char *p, *start; 290 int result; 291 int quotes = flag & (EXP_FULL | EXP_CASE); 292 293 /* 294 * This routine is slightly over-compilcated for 295 * efficiency. First we make sure there is 296 * enough space for the result, which may be bigger 297 * than the expression if we add exponentation. Next we 298 * scan backwards looking for the start of arithmetic. If the 299 * next previous character is a CTLESC character, then we 300 * have to rescan starting from the beginning since CTLESC 301 * characters have to be processed left to right. 302 */ 303 CHECKSTRSPACE(8, expdest); 304 USTPUTC('\0', expdest); 305 start = stackblock(); 306 p = expdest; 307 while (*p != CTLARI && p >= start) 308 --p; 309 if (*p != CTLARI) 310 error("missing CTLARI (shouldn't happen)"); 311 if (p > start && *(p-1) == CTLESC) 312 for (p = start; *p != CTLARI; p++) 313 if (*p == CTLESC) 314 p++; 315 if (quotes) 316 rmescapes(p+1); 317 result = arith(p+1); 318 fmtstr(p, 10, "%d", result); 319 while (*p++) 320 ; 321 result = expdest - p + 1; 322 STADJUST(-result, expdest); 323 } 324 325 326 /* 327 * Expand stuff in backwards quotes. 328 */ 329 330 STATIC void 331 expbackq(cmd, quoted, flag) 332 union node *cmd; 333 { 334 struct backcmd in; 335 int i; 336 char buf[128]; 337 char *p; 338 char *dest = expdest; 339 struct ifsregion saveifs, *savelastp; 340 struct nodelist *saveargbackq; 341 char lastc; 342 int startloc = dest - stackblock(); 343 char const *syntax = quoted? DQSYNTAX : BASESYNTAX; 344 int saveherefd; 345 int quotes = flag & (EXP_FULL | EXP_CASE); 346 347 INTOFF; 348 saveifs = ifsfirst; 349 savelastp = ifslastp; 350 saveargbackq = argbackq; 351 saveherefd = herefd; 352 herefd = -1; 353 p = grabstackstr(dest); 354 evalbackcmd(cmd, &in); 355 ungrabstackstr(p, dest); 356 ifsfirst = saveifs; 357 ifslastp = savelastp; 358 argbackq = saveargbackq; 359 herefd = saveherefd; 360 361 p = in.buf; 362 lastc = '\0'; 363 for (;;) { 364 if (--in.nleft < 0) { 365 if (in.fd < 0) 366 break; 367 while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR); 368 TRACE(("expbackq: read returns %d\n", i)); 369 if (i <= 0) 370 break; 371 p = buf; 372 in.nleft = i - 1; 373 } 374 lastc = *p++; 375 if (lastc != '\0') { 376 if (quotes && syntax[lastc] == CCTL) 377 STPUTC(CTLESC, dest); 378 STPUTC(lastc, dest); 379 } 380 } 381 if (lastc == '\n') { 382 STUNPUTC(dest); 383 } 384 if (in.fd >= 0) 385 close(in.fd); 386 if (in.buf) 387 ckfree(in.buf); 388 if (in.jp) 389 exitstatus = waitforjob(in.jp); 390 if (quoted == 0) 391 recordregion(startloc, dest - stackblock(), 0); 392 TRACE(("evalbackq: size=%d: \"%.*s\"\n", 393 (dest - stackblock()) - startloc, 394 (dest - stackblock()) - startloc, 395 stackblock() + startloc)); 396 expdest = dest; 397 INTON; 398 } 399 400 401 402 STATIC int 403 subevalvar(p, str, subtype, startloc, varflags) 404 char *p; 405 char *str; 406 int subtype; 407 int startloc; 408 int varflags; 409 { 410 411 char *startp; 412 char *loc; 413 int c = 0; 414 int saveherefd = herefd; 415 struct nodelist *saveargbackq = argbackq; 416 herefd = -1; 417 argstr(p, 0); 418 STACKSTRNUL(expdest); 419 herefd = saveherefd; 420 argbackq = saveargbackq; 421 startp = stackblock() + startloc; 422 423 switch (subtype) { 424 case VSASSIGN: 425 setvar(str, startp, 0); 426 STADJUST(startp - expdest, expdest); 427 varflags &= ~VSNUL; 428 if (c != 0) 429 *loc = c; 430 return 1; 431 432 case VSQUESTION: 433 if (*p != CTLENDVAR) { 434 outfmt(&errout, "%s\n", startp); 435 error((char *)NULL); 436 } 437 error("%.*s: parameter %snot set", p - str - 1, 438 str, (varflags & VSNUL) ? "null or " 439 : nullstr); 440 return 0; 441 442 case VSTRIMLEFT: 443 for (loc = startp; loc < str - 1; loc++) { 444 c = *loc; 445 *loc = '\0'; 446 if (patmatch(str, startp)) { 447 *loc = c; 448 goto recordleft; 449 } 450 *loc = c; 451 } 452 return 0; 453 454 case VSTRIMLEFTMAX: 455 for (loc = str - 1; loc >= startp; loc--) { 456 c = *loc; 457 *loc = '\0'; 458 if (patmatch(str, startp)) { 459 *loc = c; 460 goto recordleft; 461 } 462 *loc = c; 463 } 464 return 0; 465 466 case VSTRIMRIGHT: 467 for (loc = str - 1; loc >= startp; loc--) { 468 if (patmatch(str, loc)) { 469 expdest = loc; 470 return 1; 471 } 472 } 473 return 0; 474 475 case VSTRIMRIGHTMAX: 476 for (loc = startp; loc < str - 1; loc++) { 477 if (patmatch(str, loc)) { 478 expdest = loc; 479 return 1; 480 } 481 } 482 return 0; 483 484 485 default: 486 abort(); 487 } 488 489 recordleft: 490 expdest = (str - 1) - (loc - startp); 491 while (loc != str - 1) 492 *startp++ = *loc++; 493 return 1; 494 } 495 496 497 /* 498 * Expand a variable, and return a pointer to the next character in the 499 * input string. 500 */ 501 502 STATIC char * 503 evalvar(p, flag) 504 char *p; 505 { 506 int subtype; 507 int varflags; 508 char *var; 509 char *val; 510 char *pat; 511 int c; 512 int set; 513 int special; 514 int startloc; 515 int varlen; 516 int easy; 517 int quotes = flag & (EXP_FULL | EXP_CASE); 518 519 varflags = *p++; 520 subtype = varflags & VSTYPE; 521 var = p; 522 special = 0; 523 if (! is_name(*p)) 524 special = 1; 525 p = strchr(p, '=') + 1; 526 again: /* jump here after setting a variable with ${var=text} */ 527 if (special) { 528 set = varisset(*var); 529 val = NULL; 530 } else { 531 val = lookupvar(var); 532 if (val == NULL || (varflags & VSNUL) && val[0] == '\0') { 533 val = NULL; 534 set = 0; 535 } else 536 set = 1; 537 } 538 varlen = 0; 539 startloc = expdest - stackblock(); 540 if (set && subtype != VSPLUS) { 541 /* insert the value of the variable */ 542 if (special) { 543 char *exp, *oexpdest = expdest; 544 varvalue(*var, varflags & VSQUOTE, flag & EXP_FULL); 545 if (subtype == VSLENGTH) { 546 for (exp = oexpdest;exp != expdest; exp++) 547 varlen++; 548 expdest = oexpdest; 549 } 550 } else { 551 char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX 552 : BASESYNTAX; 553 554 if (subtype == VSLENGTH) { 555 for (;*val; val++) 556 varlen++; 557 } 558 else { 559 while (*val) { 560 if (quotes && syntax[*val] == CCTL) 561 STPUTC(CTLESC, expdest); 562 STPUTC(*val++, expdest); 563 } 564 565 } 566 } 567 } 568 569 if (subtype == VSPLUS) 570 set = ! set; 571 572 easy = ((varflags & VSQUOTE) == 0 || 573 (*var == '@' && shellparam.nparam != 1)); 574 575 576 switch (subtype) { 577 case VSLENGTH: 578 expdest = cvtnum(varlen, expdest); 579 goto record; 580 581 case VSNORMAL: 582 if (!easy) 583 break; 584 record: 585 recordregion(startloc, expdest - stackblock(), 586 varflags & VSQUOTE); 587 break; 588 589 case VSPLUS: 590 case VSMINUS: 591 if (!set) { 592 argstr(p, flag); 593 break; 594 } 595 if (easy) 596 goto record; 597 break; 598 599 case VSTRIMLEFT: 600 case VSTRIMLEFTMAX: 601 case VSTRIMRIGHT: 602 case VSTRIMRIGHTMAX: 603 if (!set) 604 break; 605 /* 606 * Terminate the string and start recording the pattern 607 * right after it 608 */ 609 STPUTC('\0', expdest); 610 pat = expdest; 611 if (subevalvar(p, pat, subtype, startloc, varflags)) 612 goto record; 613 break; 614 615 case VSASSIGN: 616 case VSQUESTION: 617 if (!set) { 618 if (subevalvar(p, var, subtype, startloc, varflags)) 619 goto again; 620 break; 621 } 622 if (easy) 623 goto record; 624 break; 625 626 default: 627 abort(); 628 } 629 630 if (subtype != VSNORMAL) { /* skip to end of alternative */ 631 int nesting = 1; 632 for (;;) { 633 if ((c = *p++) == CTLESC) 634 p++; 635 else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) { 636 if (set) 637 argbackq = argbackq->next; 638 } else if (c == CTLVAR) { 639 if ((*p++ & VSTYPE) != VSNORMAL) 640 nesting++; 641 } else if (c == CTLENDVAR) { 642 if (--nesting == 0) 643 break; 644 } 645 } 646 } 647 return p; 648 } 649 650 651 652 /* 653 * Test whether a specialized variable is set. 654 */ 655 656 STATIC int 657 varisset(name) 658 char name; 659 { 660 char **ap; 661 662 if (name == '!') { 663 if (backgndpid == -1) 664 return 0; 665 } else if (name == '@' || name == '*') { 666 if (*shellparam.p == NULL) 667 return 0; 668 } else if ((unsigned)(name -= '1') <= '9' - '1') { 669 ap = shellparam.p; 670 do { 671 if (*ap++ == NULL) 672 return 0; 673 } while (--name >= 0); 674 } 675 return 1; 676 } 677 678 679 680 /* 681 * Add the value of a specialized variable to the stack string. 682 */ 683 684 STATIC void 685 varvalue(name, quoted, allow_split) 686 char name; 687 { 688 int num; 689 char *p; 690 int i; 691 extern int exitstatus; 692 char sep; 693 char **ap; 694 char const *syntax; 695 696 #define STRTODEST(p) \ 697 do {\ 698 if (allow_split) { \ 699 syntax = quoted? DQSYNTAX : BASESYNTAX; \ 700 while (*p) { \ 701 if (syntax[*p] == CCTL) \ 702 STPUTC(CTLESC, expdest); \ 703 STPUTC(*p++, expdest); \ 704 } \ 705 } else \ 706 while (*p) \ 707 STPUTC(*p++, expdest); \ 708 } while (0) 709 710 711 switch (name) { 712 case '$': 713 num = rootpid; 714 goto numvar; 715 case '?': 716 num = exitstatus; 717 goto numvar; 718 case '#': 719 num = shellparam.nparam; 720 goto numvar; 721 case '!': 722 num = backgndpid; 723 numvar: 724 expdest = cvtnum(num, expdest); 725 break; 726 case '-': 727 for (i = 0 ; i < NOPTS ; i++) { 728 if (optlist[i].val) 729 STPUTC(optlist[i].letter, expdest); 730 } 731 break; 732 case '@': 733 if (allow_split) { 734 sep = '\0'; 735 goto allargs; 736 } 737 /* fall through */ 738 case '*': 739 sep = ' '; 740 allargs: 741 for (ap = shellparam.p ; (p = *ap++) != NULL ; ) { 742 STRTODEST(p); 743 if (*ap) 744 STPUTC(sep, expdest); 745 } 746 break; 747 case '0': 748 p = arg0; 749 STRTODEST(p); 750 break; 751 default: 752 if ((unsigned)(name -= '1') <= '9' - '1') { 753 p = shellparam.p[name]; 754 STRTODEST(p); 755 } 756 break; 757 } 758 } 759 760 761 762 /* 763 * Record the the fact that we have to scan this region of the 764 * string for IFS characters. 765 */ 766 767 STATIC void 768 recordregion(start, end, nulonly) { 769 register struct ifsregion *ifsp; 770 771 if (ifslastp == NULL) { 772 ifsp = &ifsfirst; 773 } else { 774 ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion)); 775 ifslastp->next = ifsp; 776 } 777 ifslastp = ifsp; 778 ifslastp->next = NULL; 779 ifslastp->begoff = start; 780 ifslastp->endoff = end; 781 ifslastp->nulonly = nulonly; 782 } 783 784 785 786 /* 787 * Break the argument string into pieces based upon IFS and add the 788 * strings to the argument list. The regions of the string to be 789 * searched for IFS characters have been stored by recordregion. 790 */ 791 792 STATIC void 793 ifsbreakup(string, arglist) 794 char *string; 795 struct arglist *arglist; 796 { 797 struct ifsregion *ifsp; 798 struct strlist *sp; 799 char *start; 800 register char *p; 801 char *q; 802 char *ifs; 803 804 start = string; 805 if (ifslastp != NULL) { 806 ifsp = &ifsfirst; 807 do { 808 p = string + ifsp->begoff; 809 ifs = ifsp->nulonly? nullstr : ifsval(); 810 while (p < string + ifsp->endoff) { 811 q = p; 812 if (*p == CTLESC) 813 p++; 814 if (strchr(ifs, *p++)) { 815 if (q > start || *ifs != ' ') { 816 *q = '\0'; 817 sp = (struct strlist *)stalloc(sizeof *sp); 818 sp->text = start; 819 *arglist->lastp = sp; 820 arglist->lastp = &sp->next; 821 } 822 if (*ifs == ' ') { 823 for (;;) { 824 if (p >= string + ifsp->endoff) 825 break; 826 q = p; 827 if (*p == CTLESC) 828 p++; 829 if (strchr(ifs, *p++) == NULL) { 830 p = q; 831 break; 832 } 833 } 834 } 835 start = p; 836 } 837 } 838 } while ((ifsp = ifsp->next) != NULL); 839 if (*start || (*ifs != ' ' && start > string)) { 840 sp = (struct strlist *)stalloc(sizeof *sp); 841 sp->text = start; 842 *arglist->lastp = sp; 843 arglist->lastp = &sp->next; 844 } 845 } else { 846 sp = (struct strlist *)stalloc(sizeof *sp); 847 sp->text = start; 848 *arglist->lastp = sp; 849 arglist->lastp = &sp->next; 850 } 851 } 852 853 854 855 /* 856 * Expand shell metacharacters. At this point, the only control characters 857 * should be escapes. The results are stored in the list exparg. 858 */ 859 860 char *expdir; 861 862 863 STATIC void 864 expandmeta(str, flag) 865 struct strlist *str; 866 { 867 char *p; 868 struct strlist **savelastp; 869 struct strlist *sp; 870 char c; 871 /* TODO - EXP_REDIR */ 872 873 while (str) { 874 if (fflag) 875 goto nometa; 876 p = str->text; 877 for (;;) { /* fast check for meta chars */ 878 if ((c = *p++) == '\0') 879 goto nometa; 880 if (c == '*' || c == '?' || c == '[' || c == '!') 881 break; 882 } 883 savelastp = exparg.lastp; 884 INTOFF; 885 if (expdir == NULL) { 886 int i = strlen(str->text); 887 expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */ 888 } 889 890 expmeta(expdir, str->text); 891 ckfree(expdir); 892 expdir = NULL; 893 INTON; 894 if (exparg.lastp == savelastp) { 895 /* 896 * no matches 897 */ 898 nometa: 899 *exparg.lastp = str; 900 rmescapes(str->text); 901 exparg.lastp = &str->next; 902 } else { 903 *exparg.lastp = NULL; 904 *savelastp = sp = expsort(*savelastp); 905 while (sp->next != NULL) 906 sp = sp->next; 907 exparg.lastp = &sp->next; 908 } 909 str = str->next; 910 } 911 } 912 913 914 /* 915 * Do metacharacter (i.e. *, ?, [...]) expansion. 916 */ 917 918 STATIC void 919 expmeta(enddir, name) 920 char *enddir; 921 char *name; 922 { 923 register char *p; 924 char *q; 925 char *start; 926 char *endname; 927 int metaflag; 928 struct stat statb; 929 DIR *dirp; 930 struct dirent *dp; 931 int atend; 932 int matchdot; 933 934 metaflag = 0; 935 start = name; 936 for (p = name ; ; p++) { 937 if (*p == '*' || *p == '?') 938 metaflag = 1; 939 else if (*p == '[') { 940 q = p + 1; 941 if (*q == '!') 942 q++; 943 for (;;) { 944 if (*q == CTLESC) 945 q++; 946 if (*q == '/' || *q == '\0') 947 break; 948 if (*++q == ']') { 949 metaflag = 1; 950 break; 951 } 952 } 953 } else if (*p == '!' && p[1] == '!' && (p == name || p[-1] == '/')) { 954 metaflag = 1; 955 } else if (*p == '\0') 956 break; 957 else if (*p == CTLESC) 958 p++; 959 if (*p == '/') { 960 if (metaflag) 961 break; 962 start = p + 1; 963 } 964 } 965 if (metaflag == 0) { /* we've reached the end of the file name */ 966 if (enddir != expdir) 967 metaflag++; 968 for (p = name ; ; p++) { 969 if (*p == CTLESC) 970 p++; 971 *enddir++ = *p; 972 if (*p == '\0') 973 break; 974 } 975 if (metaflag == 0 || stat(expdir, &statb) >= 0) 976 addfname(expdir); 977 return; 978 } 979 endname = p; 980 if (start != name) { 981 p = name; 982 while (p < start) { 983 if (*p == CTLESC) 984 p++; 985 *enddir++ = *p++; 986 } 987 } 988 if (enddir == expdir) { 989 p = "."; 990 } else if (enddir == expdir + 1 && *expdir == '/') { 991 p = "/"; 992 } else { 993 p = expdir; 994 enddir[-1] = '\0'; 995 } 996 if ((dirp = opendir(p)) == NULL) 997 return; 998 if (enddir != expdir) 999 enddir[-1] = '/'; 1000 if (*endname == 0) { 1001 atend = 1; 1002 } else { 1003 atend = 0; 1004 *endname++ = '\0'; 1005 } 1006 matchdot = 0; 1007 if (start[0] == '.' || start[0] == CTLESC && start[1] == '.') 1008 matchdot++; 1009 while (! int_pending() && (dp = readdir(dirp)) != NULL) { 1010 if (dp->d_name[0] == '.' && ! matchdot) 1011 continue; 1012 if (patmatch(start, dp->d_name)) { 1013 if (atend) { 1014 scopy(dp->d_name, enddir); 1015 addfname(expdir); 1016 } else { 1017 char *q; 1018 for (p = enddir, q = dp->d_name ; *p++ = *q++ ;); 1019 p[-1] = '/'; 1020 expmeta(p, endname); 1021 } 1022 } 1023 } 1024 closedir(dirp); 1025 if (! atend) 1026 endname[-1] = '/'; 1027 } 1028 1029 1030 /* 1031 * Add a file name to the list. 1032 */ 1033 1034 STATIC void 1035 addfname(name) 1036 char *name; 1037 { 1038 char *p; 1039 struct strlist *sp; 1040 1041 p = stalloc(strlen(name) + 1); 1042 scopy(name, p); 1043 sp = (struct strlist *)stalloc(sizeof *sp); 1044 sp->text = p; 1045 *exparg.lastp = sp; 1046 exparg.lastp = &sp->next; 1047 } 1048 1049 1050 /* 1051 * Sort the results of file name expansion. It calculates the number of 1052 * strings to sort and then calls msort (short for merge sort) to do the 1053 * work. 1054 */ 1055 1056 STATIC struct strlist * 1057 expsort(str) 1058 struct strlist *str; 1059 { 1060 int len; 1061 struct strlist *sp; 1062 1063 len = 0; 1064 for (sp = str ; sp ; sp = sp->next) 1065 len++; 1066 return msort(str, len); 1067 } 1068 1069 1070 STATIC struct strlist * 1071 msort(list, len) 1072 struct strlist *list; 1073 { 1074 struct strlist *p, *q; 1075 struct strlist **lpp; 1076 int half; 1077 int n; 1078 1079 if (len <= 1) 1080 return list; 1081 half = len >> 1; 1082 p = list; 1083 for (n = half ; --n >= 0 ; ) { 1084 q = p; 1085 p = p->next; 1086 } 1087 q->next = NULL; /* terminate first half of list */ 1088 q = msort(list, half); /* sort first half of list */ 1089 p = msort(p, len - half); /* sort second half */ 1090 lpp = &list; 1091 for (;;) { 1092 if (strcmp(p->text, q->text) < 0) { 1093 *lpp = p; 1094 lpp = &p->next; 1095 if ((p = *lpp) == NULL) { 1096 *lpp = q; 1097 break; 1098 } 1099 } else { 1100 *lpp = q; 1101 lpp = &q->next; 1102 if ((q = *lpp) == NULL) { 1103 *lpp = p; 1104 break; 1105 } 1106 } 1107 } 1108 return list; 1109 } 1110 1111 1112 1113 /* 1114 * Returns true if the pattern matches the string. 1115 */ 1116 1117 int 1118 patmatch(pattern, string) 1119 char *pattern; 1120 char *string; 1121 { 1122 #ifdef notdef 1123 if (pattern[0] == '!' && pattern[1] == '!') 1124 return 1 - pmatch(pattern + 2, string); 1125 else 1126 #endif 1127 return pmatch(pattern, string); 1128 } 1129 1130 1131 STATIC int 1132 pmatch(pattern, string) 1133 char *pattern; 1134 char *string; 1135 { 1136 register char *p, *q; 1137 register char c; 1138 1139 p = pattern; 1140 q = string; 1141 for (;;) { 1142 switch (c = *p++) { 1143 case '\0': 1144 goto breakloop; 1145 case CTLESC: 1146 if (*q++ != *p++) 1147 return 0; 1148 break; 1149 case '?': 1150 if (*q++ == '\0') 1151 return 0; 1152 break; 1153 case '*': 1154 c = *p; 1155 if (c != CTLESC && c != '?' && c != '*' && c != '[') { 1156 while (*q != c) { 1157 if (*q == '\0') 1158 return 0; 1159 q++; 1160 } 1161 } 1162 do { 1163 if (pmatch(p, q)) 1164 return 1; 1165 } while (*q++ != '\0'); 1166 return 0; 1167 case '[': { 1168 char *endp; 1169 int invert, found; 1170 char chr; 1171 1172 endp = p; 1173 if (*endp == '!') 1174 endp++; 1175 for (;;) { 1176 if (*endp == '\0') 1177 goto dft; /* no matching ] */ 1178 if (*endp == CTLESC) 1179 endp++; 1180 if (*++endp == ']') 1181 break; 1182 } 1183 invert = 0; 1184 if (*p == '!') { 1185 invert++; 1186 p++; 1187 } 1188 found = 0; 1189 chr = *q++; 1190 c = *p++; 1191 do { 1192 if (c == CTLESC) 1193 c = *p++; 1194 if (*p == '-' && p[1] != ']') { 1195 p++; 1196 if (*p == CTLESC) 1197 p++; 1198 if (chr >= c && chr <= *p) 1199 found = 1; 1200 p++; 1201 } else { 1202 if (chr == c) 1203 found = 1; 1204 } 1205 } while ((c = *p++) != ']'); 1206 if (found == invert) 1207 return 0; 1208 break; 1209 } 1210 dft: default: 1211 if (*q++ != c) 1212 return 0; 1213 break; 1214 } 1215 } 1216 breakloop: 1217 if (*q != '\0') 1218 return 0; 1219 return 1; 1220 } 1221 1222 1223 1224 /* 1225 * Remove any CTLESC characters from a string. 1226 */ 1227 1228 void 1229 rmescapes(str) 1230 char *str; 1231 { 1232 register char *p, *q; 1233 1234 p = str; 1235 while (*p != CTLESC) { 1236 if (*p++ == '\0') 1237 return; 1238 } 1239 q = p; 1240 while (*p) { 1241 if (*p == CTLESC) 1242 p++; 1243 *q++ = *p++; 1244 } 1245 *q = '\0'; 1246 } 1247 1248 1249 1250 /* 1251 * See if a pattern matches in a case statement. 1252 */ 1253 1254 int 1255 casematch(pattern, val) 1256 union node *pattern; 1257 char *val; 1258 { 1259 struct stackmark smark; 1260 int result; 1261 char *p; 1262 1263 setstackmark(&smark); 1264 argbackq = pattern->narg.backquote; 1265 STARTSTACKSTR(expdest); 1266 ifslastp = NULL; 1267 argstr(pattern->narg.text, EXP_TILDE | EXP_CASE); 1268 STPUTC('\0', expdest); 1269 p = grabstackstr(expdest); 1270 result = patmatch(p, val); 1271 popstackmark(&smark); 1272 return result; 1273 } 1274 1275 /* 1276 * Our own itoa(). 1277 */ 1278 1279 STATIC char * 1280 cvtnum(num, buf) 1281 int num; 1282 char *buf; 1283 { 1284 char temp[32]; 1285 int neg = num < 0; 1286 char *p = temp + 31; 1287 1288 temp[31] = '\0'; 1289 1290 do { 1291 *--p = num % 10 + '0'; 1292 } while ((num /= 10) != 0); 1293 1294 if (neg) 1295 *--p = '-'; 1296 1297 while (*p) 1298 STPUTC(*p++, buf); 1299 return buf; 1300 } 1301