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