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 */
added
removed
braces.c
