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