]>
git.ipfire.org Git - thirdparty/bash.git/blob - braces.c
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 typedef char *WORD_DESC
;
44 typedef char **WORD_LIST
;
49 #include "typemax.h" /* INTMAX_MIN, INTMAX_MAX */
52 #include "chartypes.h"
58 #define brace_whitespace(c) (!(c) || (c) == ' ' || (c) == '\t' || (c) == '\n')
60 #define BRACE_SEQ_SPECIFIER ".."
62 extern int asprintf
__P((char **, const char *, ...)) __attribute__((__format__ (printf
, 2, 3)));
64 extern int last_command_exit_value
;
68 Segregate the text into 3 sections: preamble (stuff before an open brace),
69 postamble (stuff after the matching close brace) and amble (stuff after
70 preamble, and before postamble). Expand amble, and then tack on the
71 expansions to preamble. Expand postamble, and tack on the expansions to
75 /* The character which is used to separate arguments. */
76 static const int brace_arg_separator
= ',';
79 static int brace_gobbler
__P((char *, size_t, int *, int));
80 static char **expand_amble
__P((char *, size_t, int));
81 static char **expand_seqterm
__P((char *, size_t));
82 static char **mkseq
__P((intmax_t, intmax_t, intmax_t, int, int));
83 static char **array_concat
__P((char **, char **));
85 static int brace_gobbler ();
86 static char **expand_amble ();
87 static char **expand_seqterm ();
88 static char **mkseq();
89 static char **array_concat ();
99 for (i
= 0; a
[i
]; i
++)
100 printf ("dump_result: a[%d] = -%s-\n", i
, a
[i
]);
104 /* Return an array of strings; the brace expansion of TEXT. */
111 char *preamble
, *postamble
, *amble
;
113 char **tack
, **result
;
118 /* Find the text of the preamble. */
119 tlen
= strlen (text
);
121 #if defined (CSH_BRACE_COMPAT)
122 c
= brace_gobbler (text
, tlen
, &i
, '{'); /* } */
124 /* Make sure that when we exit this loop, c == 0 or text[i] begins a
125 valid brace expansion sequence. */
128 c
= brace_gobbler (text
, tlen
, &i
, '{'); /* } */
130 /* Verify that c begins a valid brace expansion word. If it doesn't, we
131 go on. Loop stops when there are no more open braces in the word. */
134 start
= j
= i
+ 1; /* { */
135 c
= brace_gobbler (text
, tlen
, &j
, '}');
136 if (c
== 0) /* it's not */
152 #endif /* !CSH_BRACE_COMPAT */
154 preamble
= (char *)xmalloc (i
+ 1);
156 strncpy (preamble
, text
, i
);
159 result
= (char **)xmalloc (2 * sizeof (char *));
160 result
[0] = preamble
;
161 result
[1] = (char *)NULL
;
163 /* Special case. If we never found an exciting character, then
164 the preamble is all of the text, so just return that. */
168 /* Find the amble. This is the stuff inside this set of braces. */
170 c
= brace_gobbler (text
, tlen
, &i
, '}');
172 /* What if there isn't a matching close brace? */
176 /* Well, if we found an unquoted BRACE_ARG_SEPARATOR between START
177 and I, then this should be an error. Otherwise, it isn't. */
184 ADVANCE_CHAR (text
, tlen
, j
);
188 if (text
[j
] == brace_arg_separator
)
190 strvec_dispose (result
);
191 last_command_exit_value
= 1;
192 report_error ("no closing `%c' in %s", '}', text
);
193 throw_to_top_level ();
195 ADVANCE_CHAR (text
, tlen
, j
);
198 free (preamble
); /* Same as result[0]; see initialization. */
199 result
[0] = savestring (text
);
204 amble
= substring (text
, start
, i
);
207 amble
= (char *)xmalloc (1 + (i
- start
));
208 strncpy (amble
, &text
[start
], (i
- start
));
216 /* If the amble does not contain an unquoted BRACE_ARG_SEPARATOR, then
217 just return without doing any expansion. */
221 if (amble
[j
] == '\\')
224 ADVANCE_CHAR (amble
, alen
, j
);
228 if (amble
[j
] == brace_arg_separator
)
231 ADVANCE_CHAR (amble
, alen
, j
);
236 tack
= expand_seqterm (amble
, alen
);
239 else if (text
[i
+ 1])
241 /* If the sequence expansion fails (e.g., because the integers
242 overflow), but there is more in the string, try and process
243 the rest of the string, which may contain additional brace
244 expansions. Treat the unexpanded sequence term as a simple
245 string (including the braces). */
246 tack
= strvec_create (2);
247 tack
[0] = savestring (text
+start
-1);
248 tack
[0][i
-start
+2] = '\0';
256 result
[0] = savestring (text
);
262 tack
= expand_amble (amble
, alen
, 0);
264 result
= array_concat (result
, tack
);
267 strvec_dispose (tack
);
269 postamble
= text
+ i
+ 1;
271 if (postamble
&& *postamble
)
273 tack
= brace_expand (postamble
);
274 result
= array_concat (result
, tack
);
276 strvec_dispose (tack
);
282 /* Expand the text found inside of braces. We simply try to split the
283 text at BRACE_ARG_SEPARATORs into separate strings. We then brace
284 expand each slot which needs it, until there are no more slots which
287 expand_amble (text
, tlen
, flags
)
292 char **result
, **partial
, **tresult
;
300 result
= (char **)NULL
;
306 c
= brace_gobbler (text
, tlen
, &i
, brace_arg_separator
);
308 tem
= substring (text
, start
, i
);
310 tem
= (char *)xmalloc (1 + (i
- start
));
311 strncpy (tem
, &text
[start
], (i
- start
));
312 tem
[i
- start
] = '\0';
315 partial
= brace_expand (tem
);
321 register int lr
, lp
, j
;
323 lr
= strvec_len (result
);
324 lp
= strvec_len (partial
);
326 tresult
= strvec_mresize (result
, lp
+ lr
+ 1);
329 internal_error (_("brace expansion: cannot allocate memory for %s"), tem
);
331 strvec_dispose (partial
);
332 strvec_dispose (result
);
333 result
= (char **)NULL
;
339 for (j
= 0; j
< lp
; j
++)
340 result
[lr
+ j
] = partial
[j
];
342 result
[lr
+ j
] = (char *)NULL
;
347 ADVANCE_CHAR (text
, tlen
, i
);
362 # define sh_imaxabs(x) (((x) >= 0) ? (x) : -(x))
365 /* Handle signed arithmetic overflow and underflow. Have to do it this way
366 to avoid compilers optimizing out simpler overflow checks. */
368 /* Make sure that a+b does not exceed MAXV or is smaller than MINV (if b < 0).
369 Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
370 #define ADDOVERFLOW(a,b,minv,maxv) \
371 ((((a) > 0) && ((b) > ((maxv) - (a)))) || \
372 (((a) < 0) && ((b) < ((minv) - (a)))))
374 /* Make sure that a-b is not smaller than MINV or exceeds MAXV (if b < 0).
375 Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
376 #define SUBOVERFLOW(a,b,minv,maxv) \
377 ((((b) > 0) && ((a) < ((minv) + (b)))) || \
378 (((b) < 0) && ((a) > ((maxv) + (b)))))
381 mkseq (start
, end
, incr
, type
, width
)
382 intmax_t start
, end
, incr
;
392 if (start
> end
&& incr
> 0)
394 else if (start
< end
&& incr
< 0)
396 if (incr
== INTMAX_MIN
) /* Don't use -INTMAX_MIN */
397 return ((char **)NULL
);
401 /* Check that end-start will not overflow INTMAX_MIN, INTMAX_MAX. The +3
402 and -2, not strictly necessary, are there because of the way the number
403 of elements and value passed to strvec_create() are calculated below. */
404 if (SUBOVERFLOW (end
, start
, INTMAX_MIN
+3, INTMAX_MAX
-2))
405 return ((char **)NULL
);
407 prevn
= sh_imaxabs (end
- start
);
408 /* Need to check this way in case INT_MAX == INTMAX_MAX */
409 if (INT_MAX
== INTMAX_MAX
&& (ADDOVERFLOW (prevn
, 2, INT_MIN
, INT_MAX
)))
410 return ((char **)NULL
);
411 /* Make sure the assignment to nelem below doesn't end up <= 0 due to
413 else if (ADDOVERFLOW ((prevn
/sh_imaxabs(incr
)), 1, INTMAX_MIN
, INTMAX_MAX
))
414 return ((char **)NULL
);
416 /* XXX - TOFIX: potentially allocating a lot of extra memory if
417 imaxabs(incr) != 1 */
418 /* Instead of a simple nelem = prevn + 1, something like:
419 nelem = (prevn / imaxabs(incr)) + 1;
421 nelem
= (prevn
/ sh_imaxabs(incr
)) + 1;
422 if (nelem
> INT_MAX
- 2) /* Don't overflow int */
423 return ((char **)NULL
);
424 result
= strvec_mcreate (nelem
+ 1);
427 internal_error (_("brace expansion: failed to allocate memory for %d elements"), nelem
);
428 return ((char **)NULL
);
431 /* Make sure we go through the loop at least once, so {3..3} prints `3' */
439 strvec_dispose (result
);
440 result
= (char **)NULL
;
445 result
[i
++] = t
= itos (n
);
446 else if (type
== ST_ZINT
)
450 len
= asprintf (&t
, "%0*d", width
, arg
);
455 if (t
= (char *)malloc (2))
463 /* We failed to allocate memory for this number, so we bail. */
466 char *p
, lbuf
[INT_STRLEN_BOUND(intmax_t) + 1];
468 /* Easier to do this than mess around with various intmax_t printf
469 formats (%ld? %lld? %jd?) and PRIdMAX. */
470 p
= inttostr (n
, lbuf
, sizeof (lbuf
));
471 internal_error (_("brace expansion: failed to allocate memory for `%s'"), p
);
472 strvec_dispose (result
);
473 return ((char **)NULL
);
476 /* Handle overflow and underflow of n+incr */
477 if (ADDOVERFLOW (n
, incr
, INTMAX_MIN
, INTMAX_MAX
))
482 if ((incr
< 0 && n
< end
) || (incr
> 0 && n
> end
))
487 result
[i
] = (char *)0;
492 expand_seqterm (text
, tlen
)
497 int i
, lhs_t
, rhs_t
, lhs_l
, rhs_l
, width
;
498 intmax_t lhs_v
, rhs_v
, incr
;
500 char **result
, *ep
, *oep
;
502 t
= strstr (text
, BRACE_SEQ_SPECIFIER
);
504 return ((char **)NULL
);
506 lhs_l
= t
- text
; /* index of start of BRACE_SEQ_SPECIFIER */
507 lhs
= substring (text
, 0, lhs_l
);
508 rhs
= substring (text
, lhs_l
+ sizeof(BRACE_SEQ_SPECIFIER
) - 1, tlen
);
510 if (lhs
[0] == 0 || rhs
[0] == 0)
514 return ((char **)NULL
);
517 /* Now figure out whether LHS and RHS are integers or letters. Both
518 sides have to match. */
519 lhs_t
= (legal_number (lhs
, &tl
)) ? ST_INT
:
520 ((ISALPHA (lhs
[0]) && lhs
[1] == 0) ? ST_CHAR
: ST_BAD
);
522 /* Decide on rhs and whether or not it looks like the user specified
525 if (ISDIGIT (rhs
[0]) || ((rhs
[0] == '+' || rhs
[0] == '-') && ISDIGIT (rhs
[1])))
529 tr
= strtoimax (rhs
, &ep
, 10);
530 if (errno
== ERANGE
|| (ep
&& *ep
!= 0 && *ep
!= '.'))
531 rhs_t
= ST_BAD
; /* invalid */
533 else if (ISALPHA (rhs
[0]) && (rhs
[1] == 0 || rhs
[1] == '.'))
549 if (ep
&& *ep
== '.' && ep
[1] == '.' && ep
[2])
550 incr
= strtoimax (ep
+ 2, &ep
, 10);
551 if (*ep
!= 0 || errno
== ERANGE
)
552 rhs_t
= ST_BAD
; /* invalid incr or overflow */
556 if (lhs_t
!= rhs_t
|| lhs_t
== ST_BAD
|| rhs_t
== ST_BAD
)
560 return ((char **)NULL
);
563 /* OK, we have something. It's either a sequence of integers, ascending
564 or descending, or a sequence or letters, ditto. Generate the sequence,
565 put it into a string vector, and return it. */
567 if (lhs_t
== ST_CHAR
)
569 lhs_v
= (unsigned char)lhs
[0];
570 rhs_v
= (unsigned char)rhs
[0];
575 lhs_v
= tl
; /* integer truncation */
578 /* Decide whether or not the terms need zero-padding */
579 rhs_l
= tlen
- lhs_l
- sizeof (BRACE_SEQ_SPECIFIER
) + 1;
581 if (lhs_l
> 1 && lhs
[0] == '0')
582 width
= lhs_l
, lhs_t
= ST_ZINT
;
583 if (lhs_l
> 2 && lhs
[0] == '-' && lhs
[1] == '0')
584 width
= lhs_l
, lhs_t
= ST_ZINT
;
585 if (rhs_l
> 1 && rhs
[0] == '0' && width
< rhs_l
)
586 width
= rhs_l
, lhs_t
= ST_ZINT
;
587 if (rhs_l
> 2 && rhs
[0] == '-' && rhs
[1] == '0' && width
< rhs_l
)
588 width
= rhs_l
, lhs_t
= ST_ZINT
;
590 if (width
< lhs_l
&& lhs_t
== ST_ZINT
)
592 if (width
< rhs_l
&& lhs_t
== ST_ZINT
)
596 result
= mkseq (lhs_v
, rhs_v
, incr
, lhs_t
, width
);
604 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
605 index of the character matching SATISFY. This understands about
606 quoting. Return the character that caused us to stop searching;
607 this is either the same as SATISFY, or 0. */
608 /* If SATISFY is `}', we are looking for a brace expression, so we
609 should enforce the rules that govern valid brace expansions:
610 1) to count as an arg separator, a comma or `..' has to be outside
611 an inner set of braces.
614 brace_gobbler (text
, tlen
, indx
, satisfy
)
620 register int i
, c
, quoted
, level
, commas
, pass_next
;
627 level
= quoted
= pass_next
= 0;
628 #if defined (CSH_BRACE_COMPAT)
631 commas
= (satisfy
== '}') ? 0 : 1;
641 ADVANCE_CHAR (text
, tlen
, i
);
648 /* A backslash escapes the next character. This allows backslash to
649 escape the quote character in a double-quoted string. */
650 if (c
== '\\' && (quoted
== 0 || quoted
== '"' || quoted
== '`'))
658 /* If compiling for the shell, treat ${...} like \{...} */
659 if (c
== '$' && text
[i
+1] == '{' && quoted
!= '\'') /* } */
674 /* The shell allows quoted command substitutions */
675 if (quoted
== '"' && c
== '$' && text
[i
+1] == '(') /*)*/
679 ADVANCE_CHAR (text
, tlen
, i
);
686 if (c
== '"' || c
== '\'' || c
== '`')
694 /* Pass new-style command and process substitutions through unchanged. */
695 if ((c
== '$' || c
== '<' || c
== '>') && text
[i
+1] == '(') /* ) */
699 t
= extract_command_subst (text
, &si
, 0);
707 if (c
== satisfy
&& level
== 0 && quoted
== 0 && commas
> 0)
709 /* We ignore an open brace surrounded by whitespace, and also
710 an open brace followed immediately by a close brace preceded
713 ((!i
|| brace_whitespace (text
[i
- 1])) &&
714 (brace_whitespace (text
[i
+ 1]) || text
[i
+ 1] == '}')))
725 else if (c
== '}' && level
)
727 #if !defined (CSH_BRACE_COMPAT)
728 else if (satisfy
== '}' && c
== brace_arg_separator
&& level
== 0)
730 else if (satisfy
== '}' && STREQN (text
+i
, BRACE_SEQ_SPECIFIER
, 2) &&
731 text
[i
+2] != satisfy
&& level
== 0)
736 ADVANCE_CHAR (text
, tlen
, i
);
746 /* Return 1 if ARR has any non-empty-string members. Used to short-circuit
747 in array_concat() below. */
749 degenerate_array (arr
)
754 for (i
= 0; arr
[i
]; i
++)
755 if (arr
[i
][0] != '\0')
760 /* Return a new array of strings which is the result of appending each
761 string in ARR2 to each string in ARR1. The resultant array is
762 len (arr1) * len (arr2) long. For convenience, ARR1 (and its contents)
763 are free ()'ed. ARR1 can be NULL, in that case, a new version of ARR2
766 array_concat (arr1
, arr2
)
769 register int i
, j
, len
, len1
, len2
;
770 register char **result
;
773 return (arr2
); /* XXX - see if we can get away without copying? */
776 return (arr1
); /* XXX - caller expects us to free arr1 */
778 /* We can only short-circuit if the array consists of a single null element;
779 otherwise we need to replicate the contents of the other array and
780 prefix (or append, below) an empty element to each one. */
781 if (arr1
[0] && arr1
[0][0] == 0 && arr1
[1] == 0)
783 strvec_dispose (arr1
);
784 return (arr2
); /* XXX - use flags to see if we can avoid copying here */
787 if (arr2
[0] && arr2
[0][0] == 0 && arr2
[1] == 0)
788 return (arr1
); /* XXX - rather than copying and freeing it */
790 len1
= strvec_len (arr1
);
791 len2
= strvec_len (arr2
);
793 result
= (char **)xmalloc ((1 + (len1
* len2
)) * sizeof (char *));
796 for (i
= 0; i
< len1
; i
++)
798 int strlen_1
= strlen (arr1
[i
]);
800 for (j
= 0; j
< len2
; j
++)
802 result
[len
] = (char *)xmalloc (1 + strlen_1
+ strlen (arr2
[j
]));
803 strcpy (result
[len
], arr1
[i
]);
804 strcpy (result
[len
] + strlen_1
, arr2
[j
]);
811 result
[len
] = (char *)NULL
;
830 return (realloc (p
, n
));
834 internal_error (format
, arg1
, arg2
)
835 char *format
, *arg1
, *arg2
;
837 fprintf (stderr
, format
, arg1
, arg2
);
838 fprintf (stderr
, "\n");
850 fprintf (stderr
, "brace_expand> ");
852 if ((!fgets (example
, 256, stdin
)) ||
853 (strncmp (example
, "quit", 4) == 0))
856 if (strlen (example
))
857 example
[strlen (example
) - 1] = '\0';
859 result
= brace_expand (example
);
861 for (i
= 0; result
[i
]; i
++)
862 printf ("%s\n", result
[i
]);
864 strvec_dispose (result
);
870 * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
875 #endif /* BRACE_EXPANSION */