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