1 /* braces.c -- code for doing word expansion in curly braces. */
3 /* Copyright (C) 1987-2012 Free Software Foundation, Inc.
5 This file is part of GNU Bash, the Bourne Again SHell.
7 Bash is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Bash is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with Bash. If not, see <http://www.gnu.org/licenses/>.
21 /* Stuff in curly braces gets expanded before all other shell expansions. */
25 #if defined (BRACE_EXPANSION)
27 #if defined (HAVE_UNISTD_H)
29 # include <sys/types.h>
43 #include "typemax.h" /* INTMAX_MIN, INTMAX_MAX */
46 #include "chartypes.h"
52 #define brace_whitespace(c) (!(c) || (c) == ' ' || (c) == '\t' || (c) == '\n')
54 #define BRACE_SEQ_SPECIFIER ".."
56 extern int asprintf __P((char **, const char *, ...)) __attribute__((__format__ (printf, 2, 3)));
58 extern int last_command_exit_value;
62 Segregate the text into 3 sections: preamble (stuff before an open brace),
63 postamble (stuff after the matching close brace) and amble (stuff after
64 preamble, and before postamble). Expand amble, and then tack on the
65 expansions to preamble. Expand postamble, and tack on the expansions to
69 /* The character which is used to separate arguments. */
70 static const int brace_arg_separator = ',';
73 static int brace_gobbler __P((char *, size_t, int *, int));
74 static char **expand_amble __P((char *, size_t, int));
75 static char **expand_seqterm __P((char *, size_t));
76 static char **mkseq __P((intmax_t, intmax_t, intmax_t, int, int));
77 static char **array_concat __P((char **, char **));
79 static int brace_gobbler ();
80 static char **expand_amble ();
81 static char **expand_seqterm ();
82 static char **mkseq();
83 static char **array_concat ();
93 for (i = 0; a[i]; i++)
94 printf ("dump_result: a[%d] = -%s-\n", i, a[i]);
98 /* Return an array of strings; the brace expansion of TEXT. */
105 char *preamble, *postamble, *amble;
107 char **tack, **result;
112 /* Find the text of the preamble. */
113 tlen = strlen (text);
115 #if defined (CSH_BRACE_COMPAT)
116 c = brace_gobbler (text, tlen, &i, '{'); /* } */
118 /* Make sure that when we exit this loop, c == 0 or text[i] begins a
119 valid brace expansion sequence. */
122 c = brace_gobbler (text, tlen, &i, '{'); /* } */
124 /* Verify that c begins a valid brace expansion word. If it doesn't, we
125 go on. Loop stops when there are no more open braces in the word. */
128 start = j = i + 1; /* { */
129 c = brace_gobbler (text, tlen, &j, '}');
130 if (c == 0) /* it's not */
146 #endif /* !CSH_BRACE_COMPAT */
148 preamble = (char *)xmalloc (i + 1);
150 strncpy (preamble, text, i);
153 result = (char **)xmalloc (2 * sizeof (char *));
154 result[0] = preamble;
155 result[1] = (char *)NULL;
157 /* Special case. If we never found an exciting character, then
158 the preamble is all of the text, so just return that. */
162 /* Find the amble. This is the stuff inside this set of braces. */
164 c = brace_gobbler (text, tlen, &i, '}');
166 /* What if there isn't a matching close brace? */
170 /* Well, if we found an unquoted BRACE_ARG_SEPARATOR between START
171 and I, then this should be an error. Otherwise, it isn't. */
178 ADVANCE_CHAR (text, tlen, j);
182 if (text[j] == brace_arg_separator)
184 strvec_dispose (result);
185 last_command_exit_value = 1;
186 report_error ("no closing `%c' in %s", '}', text);
187 throw_to_top_level ();
189 ADVANCE_CHAR (text, tlen, j);
192 free (preamble); /* Same as result[0]; see initialization. */
193 result[0] = savestring (text);
198 amble = substring (text, start, i);
201 amble = (char *)xmalloc (1 + (i - start));
202 strncpy (amble, &text[start], (i - start));
210 /* If the amble does not contain an unquoted BRACE_ARG_SEPARATOR, then
211 just return without doing any expansion. */
215 if (amble[j] == '\\')
218 ADVANCE_CHAR (amble, alen, j);
222 if (amble[j] == brace_arg_separator)
225 ADVANCE_CHAR (amble, alen, j);
230 tack = expand_seqterm (amble, alen);
233 else if (text[i + 1])
235 /* If the sequence expansion fails (e.g., because the integers
236 overflow), but there is more in the string, try and process
237 the rest of the string, which may contain additional brace
238 expansions. Treat the unexpanded sequence term as a simple
239 string (including the braces). */
240 tack = strvec_create (2);
241 tack[0] = savestring (text+start-1);
242 tack[0][i-start+2] = '\0';
250 result[0] = savestring (text);
256 tack = expand_amble (amble, alen, 0);
258 result = array_concat (result, tack);
261 strvec_dispose (tack);
263 postamble = text + i + 1;
265 if (postamble && *postamble)
267 tack = brace_expand (postamble);
268 result = array_concat (result, tack);
270 strvec_dispose (tack);
276 /* Expand the text found inside of braces. We simply try to split the
277 text at BRACE_ARG_SEPARATORs into separate strings. We then brace
278 expand each slot which needs it, until there are no more slots which
281 expand_amble (text, tlen, flags)
286 char **result, **partial, **tresult;
292 result = (char **)NULL;
298 c = brace_gobbler (text, tlen, &i, brace_arg_separator);
300 tem = substring (text, start, i);
302 tem = (char *)xmalloc (1 + (i - start));
303 strncpy (tem, &text[start], (i - start));
304 tem[i- start] = '\0';
307 partial = brace_expand (tem);
313 register int lr, lp, j;
315 lr = strvec_len (result);
316 lp = strvec_len (partial);
318 tresult = strvec_mresize (result, lp + lr + 1);
321 internal_error (_("brace expansion: cannot allocate memory for %s"), tem);
322 strvec_dispose (result);
323 result = (char **)NULL;
329 for (j = 0; j < lp; j++)
330 result[lr + j] = partial[j];
332 result[lr + j] = (char *)NULL;
336 ADVANCE_CHAR (text, tlen, i);
348 # define sh_imaxabs(x) (((x) >= 0) ? (x) : -(x))
351 /* Handle signed arithmetic overflow and underflow. Have to do it this way
352 to avoid compilers optimizing out simpler overflow checks. */
354 /* Make sure that a+b does not exceed MAXV or is smaller than MINV (if b < 0).
355 Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
356 #define ADDOVERFLOW(a,b,minv,maxv) \
357 ((((a) > 0) && ((b) > ((maxv) - (a)))) || \
358 (((a) < 0) && ((b) < ((minv) - (a)))))
360 /* Make sure that a-b is not smaller than MINV or exceeds MAXV (if b < 0).
361 Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
362 #define SUBOVERFLOW(a,b,minv,maxv) \
363 ((((b) > 0) && ((a) < ((minv) + (b)))) || \
364 (((b) < 0) && ((a) > ((maxv) + (b)))))
367 mkseq (start, end, incr, type, width)
368 intmax_t start, end, incr;
378 if (start > end && incr > 0)
380 else if (start < end && incr < 0)
382 if (incr == INTMAX_MIN) /* Don't use -INTMAX_MIN */
383 return ((char **)NULL);
387 /* Check that end-start will not overflow INTMAX_MIN, INTMAX_MAX. The +3
388 and -2, not strictly necessary, are there because of the way the number
389 of elements and value passed to strvec_create() are calculated below. */
390 if (SUBOVERFLOW (end, start, INTMAX_MIN+3, INTMAX_MAX-2))
391 return ((char **)NULL);
393 prevn = sh_imaxabs (end - start);
394 /* Need to check this way in case INT_MAX == INTMAX_MAX */
395 if (INT_MAX == INTMAX_MAX && (ADDOVERFLOW (prevn, 2, INT_MIN, INT_MAX)))
396 return ((char **)NULL);
397 /* Make sure the assignment to nelem below doesn't end up <= 0 due to
399 else if (ADDOVERFLOW ((prevn/sh_imaxabs(incr)), 1, INTMAX_MIN, INTMAX_MAX))
400 return ((char **)NULL);
402 /* XXX - TOFIX: potentially allocating a lot of extra memory if
403 imaxabs(incr) != 1 */
404 /* Instead of a simple nelem = prevn + 1, something like:
405 nelem = (prevn / imaxabs(incr)) + 1;
407 nelem = (prevn / sh_imaxabs(incr)) + 1;
408 if (nelem > INT_MAX - 2) /* Don't overflow int */
409 return ((char **)NULL);
410 result = strvec_mcreate (nelem + 1);
413 internal_error (_("brace expansion: failed to allocate memory for %d elements"), nelem);
414 return ((char **)NULL);
417 /* Make sure we go through the loop at least once, so {3..3} prints `3' */
423 QUIT; /* XXX - memory leak here */
426 result[i++] = t = itos (n);
427 else if (type == ST_ZINT)
431 len = asprintf (&t, "%0*d", width, arg);
436 if (t = (char *)malloc (2))
444 /* We failed to allocate memory for this number, so we bail. */
447 char *p, lbuf[INT_STRLEN_BOUND(intmax_t) + 1];
449 /* Easier to do this than mess around with various intmax_t printf
450 formats (%ld? %lld? %jd?) and PRIdMAX. */
451 p = inttostr (n, lbuf, sizeof (lbuf));
452 internal_error (_("brace expansion: failed to allocate memory for `%s'"), p);
453 strvec_dispose (result);
454 return ((char **)NULL);
457 /* Handle overflow and underflow of n+incr */
458 if (ADDOVERFLOW (n, incr, INTMAX_MIN, INTMAX_MAX))
463 if ((incr < 0 && n < end) || (incr > 0 && n > end))
468 result[i] = (char *)0;
473 expand_seqterm (text, tlen)
478 int i, lhs_t, rhs_t, lhs_l, rhs_l, width;
479 intmax_t lhs_v, rhs_v, incr;
481 char **result, *ep, *oep;
483 t = strstr (text, BRACE_SEQ_SPECIFIER);
485 return ((char **)NULL);
487 lhs_l = t - text; /* index of start of BRACE_SEQ_SPECIFIER */
488 lhs = substring (text, 0, lhs_l);
489 rhs = substring (text, lhs_l + sizeof(BRACE_SEQ_SPECIFIER) - 1, tlen);
491 if (lhs[0] == 0 || rhs[0] == 0)
495 return ((char **)NULL);
498 /* Now figure out whether LHS and RHS are integers or letters. Both
499 sides have to match. */
500 lhs_t = (legal_number (lhs, &tl)) ? ST_INT :
501 ((ISALPHA (lhs[0]) && lhs[1] == 0) ? ST_CHAR : ST_BAD);
503 /* Decide on rhs and whether or not it looks like the user specified
506 if (ISDIGIT (rhs[0]) || ((rhs[0] == '+' || rhs[0] == '-') && ISDIGIT (rhs[1])))
510 tr = strtoimax (rhs, &ep, 10);
511 if (errno == ERANGE || (ep && *ep != 0 && *ep != '.'))
512 rhs_t = ST_BAD; /* invalid */
514 else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.'))
530 if (ep && *ep == '.' && ep[1] == '.' && ep[2])
531 incr = strtoimax (ep + 2, &ep, 10);
532 if (*ep != 0 || errno == ERANGE)
533 rhs_t = ST_BAD; /* invalid incr or overflow */
537 if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
541 return ((char **)NULL);
544 /* OK, we have something. It's either a sequence of integers, ascending
545 or descending, or a sequence or letters, ditto. Generate the sequence,
546 put it into a string vector, and return it. */
548 if (lhs_t == ST_CHAR)
550 lhs_v = (unsigned char)lhs[0];
551 rhs_v = (unsigned char)rhs[0];
556 lhs_v = tl; /* integer truncation */
559 /* Decide whether or not the terms need zero-padding */
560 rhs_l = tlen - lhs_l - sizeof (BRACE_SEQ_SPECIFIER) + 1;
562 if (lhs_l > 1 && lhs[0] == '0')
563 width = lhs_l, lhs_t = ST_ZINT;
564 if (lhs_l > 2 && lhs[0] == '-' && lhs[1] == '0')
565 width = lhs_l, lhs_t = ST_ZINT;
566 if (rhs_l > 1 && rhs[0] == '0' && width < rhs_l)
567 width = rhs_l, lhs_t = ST_ZINT;
568 if (rhs_l > 2 && rhs[0] == '-' && rhs[1] == '0' && width < rhs_l)
569 width = rhs_l, lhs_t = ST_ZINT;
571 if (width < lhs_l && lhs_t == ST_ZINT)
573 if (width < rhs_l && lhs_t == ST_ZINT)
577 result = mkseq (lhs_v, rhs_v, incr, lhs_t, width);
585 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
586 index of the character matching SATISFY. This understands about
587 quoting. Return the character that caused us to stop searching;
588 this is either the same as SATISFY, or 0. */
589 /* If SATISFY is `}', we are looking for a brace expression, so we
590 should enforce the rules that govern valid brace expansions:
591 1) to count as an arg separator, a comma or `..' has to be outside
592 an inner set of braces.
595 brace_gobbler (text, tlen, indx, satisfy)
601 register int i, c, quoted, level, commas, pass_next;
608 level = quoted = pass_next = 0;
609 #if defined (CSH_BRACE_COMPAT)
612 commas = (satisfy == '}') ? 0 : 1;
621 ADVANCE_CHAR (text, tlen, i);
625 /* A backslash escapes the next character. This allows backslash to
626 escape the quote character in a double-quoted string. */
627 if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
635 /* If compiling for the shell, treat ${...} like \{...} */
636 if (c == '$' && text[i+1] == '{' && quoted != '\'') /* } */
651 /* The shell allows quoted command substitutions */
652 if (quoted == '"' && c == '$' && text[i+1] == '(') /*)*/
655 ADVANCE_CHAR (text, tlen, i);
659 if (c == '"' || c == '\'' || c == '`')
667 /* Pass new-style command and process substitutions through unchanged. */
668 if ((c == '$' || c == '<' || c == '>') && text[i+1] == '(') /* ) */
672 t = extract_command_subst (text, &si, 0);
680 if (c == satisfy && level == 0 && quoted == 0 && commas > 0)
682 /* We ignore an open brace surrounded by whitespace, and also
683 an open brace followed immediately by a close brace preceded
686 ((!i || brace_whitespace (text[i - 1])) &&
687 (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
698 else if (c == '}' && level)
700 #if !defined (CSH_BRACE_COMPAT)
701 else if (satisfy == '}' && c == brace_arg_separator && level == 0)
703 else if (satisfy == '}' && STREQN (text+i, BRACE_SEQ_SPECIFIER, 2) &&
704 text[i+2] != satisfy && level == 0)
708 ADVANCE_CHAR (text, tlen, i);
715 /* Return 1 if ARR has any non-empty-string members. Used to short-circuit
716 in array_concat() below. */
718 degenerate_array (arr)
723 for (i = 0; arr[i]; i++)
724 if (arr[i][0] != '\0')
729 /* Return a new array of strings which is the result of appending each
730 string in ARR2 to each string in ARR1. The resultant array is
731 len (arr1) * len (arr2) long. For convenience, ARR1 (and its contents)
732 are free ()'ed. ARR1 can be NULL, in that case, a new version of ARR2
735 array_concat (arr1, arr2)
738 register int i, j, len, len1, len2;
739 register char **result;
742 return (arr2); /* XXX - see if we can get away without copying? */
745 return (arr1); /* XXX - caller expects us to free arr1 */
747 /* We can only short-circuit if the array consists of a single null element;
748 otherwise we need to replicate the contents of the other array and
749 prefix (or append, below) an empty element to each one. */
750 if (arr1[0] && arr1[0][0] == 0 && arr1[1] == 0)
752 strvec_dispose (arr1);
753 return (arr2); /* XXX - use flags to see if we can avoid copying here */
756 if (arr2[0] && arr2[0][0] == 0 && arr2[1] == 0)
757 return (arr1); /* XXX - rather than copying and freeing it */
759 len1 = strvec_len (arr1);
760 len2 = strvec_len (arr2);
762 result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
765 for (i = 0; i < len1; i++)
767 int strlen_1 = strlen (arr1[i]);
769 for (j = 0; j < len2; j++)
771 result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
772 strcpy (result[len], arr1[i]);
773 strcpy (result[len] + strlen_1, arr2[j]);
780 result[len] = (char *)NULL;
787 fatal_error (format, arg1, arg2)
788 char *format, *arg1, *arg2;
790 report_error (format, arg1, arg2);
794 report_error (format, arg1, arg2)
795 char *format, *arg1, *arg2;
797 fprintf (stderr, format, arg1, arg2);
798 fprintf (stderr, "\n");
810 fprintf (stderr, "brace_expand> ");
812 if ((!fgets (example, 256, stdin)) ||
813 (strncmp (example, "quit", 4) == 0))
816 if (strlen (example))
817 example[strlen (example) - 1] = '\0';
819 result = brace_expand (example);
821 for (i = 0; result[i]; i++)
822 printf ("%s\n", result[i]);
830 * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
835 #endif /* BRACE_EXPANSION */