braces.c

   1 /* braces.c -- code for doing word expansion in curly braces. */
   2
   3 /* Copyright (C) 1987-2009 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   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.
  11
  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.
  16
  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/>.
  19 */
  20
  21 /* Stuff in curly braces gets expanded before all other shell expansions. */
  22
  23 #include "config.h"
  24
  25 #if defined (BRACE_EXPANSION)
  26
  27 #if defined (HAVE_UNISTD_H)
  28 #  ifdef _MINIX
  29 #    include <sys/types.h>
  30 #  endif
  31 #  include <unistd.h>
  32 #endif
  33
  34 #include "bashansi.h"
  35
  36 #if defined (SHELL)
  37 #  include "shell.h"
  38 #endif /* SHELL */
  39
  40 #include "general.h"
  41 #include "shmbutil.h"
  42 #include "chartypes.h"
  43
  44 #define brace_whitespace(c) (!(c) || (c) == ' ' || (c) == '\t' || (c) == '\n')
  45
  46 #define BRACE_SEQ_SPECIFIER     ".."
  47
  48 extern int asprintf __P((char **, const char *, ...)) __attribute__((__format__ (printf, 2, 3)));
  49
  50 /* Basic idea:
  51
  52    Segregate the text into 3 sections: preamble (stuff before an open brace),
  53    postamble (stuff after the matching close brace) and amble (stuff after
  54    preamble, and before postamble).  Expand amble, and then tack on the
  55    expansions to preamble.  Expand postamble, and tack on the expansions to
  56    the result so far.
  57  */
  58
  59 /* The character which is used to separate arguments. */
  60 static const int brace_arg_separator = ',';
  61
  62 #if defined (__P)
  63 static int brace_gobbler __P((char *, size_t, int *, int));
  64 static char **expand_amble __P((char *, size_t, int));
  65 static char **expand_seqterm __P((char *, size_t));
  66 static char **mkseq __P((intmax_t, intmax_t, int, int, int));
  67 static char **array_concat __P((char **, char **));
  68 #else
  69 static int brace_gobbler ();
  70 static char **expand_amble ();
  71 static char **expand_seqterm ();
  72 static char **mkseq();
  73 static char **array_concat ();
  74 #endif
  75
  76 #if 0
  77 static void
  78 dump_result (a)
  79      char **a;
  80 {
  81   int i;
  82
  83   for (i = 0; a[i]; i++)
  84     printf ("dump_result: a[%d] = -%s-\n", i, a[i]);
  85 }
  86 #endif
  87
  88 /* Return an array of strings; the brace expansion of TEXT. */
  89 char **
  90 brace_expand (text)
  91      char *text;
  92 {
  93   register int start;
  94   size_t tlen;
  95   char *preamble, *postamble, *amble;
  96   size_t alen;
  97   char **tack, **result;
  98   int i, j, c, c1;
  99
 100   DECLARE_MBSTATE;
 101
 102   /* Find the text of the preamble. */
 103   tlen = strlen (text);
 104   i = 0;
 105 #if defined (CSH_BRACE_COMPAT)
 106   c = brace_gobbler (text, tlen, &i, '{');      /* } */
 107 #else
 108   /* Make sure that when we exit this loop, c == 0 or text[i] begins a
 109      valid brace expansion sequence. */
 110   do
 111     {
 112       c = brace_gobbler (text, tlen, &i, '{');  /* } */
 113       c1 = c;
 114       /* Verify that c begins a valid brace expansion word.  If it doesn't, we
 115          go on.  Loop stops when there are no more open braces in the word. */
 116       if (c)
 117         {
 118           start = j = i + 1;    /* { */
 119           c = brace_gobbler (text, tlen, &j, '}');
 120           if (c == 0)           /* it's not */
 121             {
 122               i++;
 123               c = c1;
 124               continue;
 125             }
 126           else                  /* it is */
 127             {
 128               c = c1;
 129               break;
 130             }
 131         }
 132       else
 133         break;
 134     }
 135   while (c);
 136 #endif /* !CSH_BRACE_COMPAT */
 137
 138   preamble = (char *)xmalloc (i + 1);
 139   strncpy (preamble, text, i);
 140   preamble[i] = '\0';
 141
 142   result = (char **)xmalloc (2 * sizeof (char *));
 143   result[0] = preamble;
 144   result[1] = (char *)NULL;
 145
 146   /* Special case.  If we never found an exciting character, then
 147      the preamble is all of the text, so just return that. */
 148   if (c != '{')
 149     return (result);
 150
 151   /* Find the amble.  This is the stuff inside this set of braces. */
 152   start = ++i;
 153   c = brace_gobbler (text, tlen, &i, '}');
 154
 155   /* What if there isn't a matching close brace? */
 156   if (c == 0)
 157     {
 158 #if defined (NOTDEF)
 159       /* Well, if we found an unquoted BRACE_ARG_SEPARATOR between START
 160          and I, then this should be an error.  Otherwise, it isn't. */
 161       j = start;
 162       while (j < i)
 163         {
 164           if (text[j] == '\\')
 165             {
 166               j++;
 167               ADVANCE_CHAR (text, tlen, j);
 168               continue;
 169             }
 170
 171           if (text[j] == brace_arg_separator)
 172             {   /* { */
 173               strvec_dispose (result);
 174               report_error ("no closing `%c' in %s", '}', text);
 175               throw_to_top_level ();
 176             }
 177           ADVANCE_CHAR (text, tlen, j);
 178         }
 179 #endif
 180       free (preamble);          /* Same as result[0]; see initialization. */
 181       result[0] = savestring (text);
 182       return (result);
 183     }
 184
 185 #if defined (SHELL)
 186   amble = substring (text, start, i);
 187   alen = i - start;
 188 #else
 189   amble = (char *)xmalloc (1 + (i - start));
 190   strncpy (amble, &text[start], (i - start));
 191   alen = i - start;
 192   amble[alen] = '\0';
 193 #endif
 194
 195 #if defined (SHELL)
 196   INITIALIZE_MBSTATE;
 197
 198   /* If the amble does not contain an unquoted BRACE_ARG_SEPARATOR, then
 199      just return without doing any expansion.  */
 200   j = 0;
 201   while (amble[j])
 202     {
 203       if (amble[j] == '\\')
 204         {
 205           j++;
 206           ADVANCE_CHAR (amble, alen, j);
 207           continue;
 208         }
 209
 210       if (amble[j] == brace_arg_separator)
 211         break;
 212
 213       ADVANCE_CHAR (amble, alen, j);
 214     }
 215
 216   if (amble[j] == 0)
 217     {
 218       tack = expand_seqterm (amble, alen);
 219       if (tack)
 220         goto add_tack;
 221       else
 222         {
 223           free (amble);
 224           free (preamble);
 225           result[0] = savestring (text);
 226           return (result);
 227         }
 228     }
 229 #endif /* SHELL */
 230
 231   tack = expand_amble (amble, alen, 0);
 232 add_tack:
 233   result = array_concat (result, tack);
 234   free (amble);
 235   strvec_dispose (tack);
 236
 237   postamble = text + i + 1;
 238
 239   tack = brace_expand (postamble);
 240   result = array_concat (result, tack);
 241   strvec_dispose (tack);
 242
 243   return (result);
 244 }
 245
 246 /* Expand the text found inside of braces.  We simply try to split the
 247    text at BRACE_ARG_SEPARATORs into separate strings.  We then brace
 248    expand each slot which needs it, until there are no more slots which
 249    need it. */
 250 static char **
 251 expand_amble (text, tlen, flags)
 252      char *text;
 253      size_t tlen;
 254      int flags;
 255 {
 256   char **result, **partial;
 257   char *tem;
 258   int start, i, c;
 259
 260   DECLARE_MBSTATE;
 261
 262   result = (char **)NULL;
 263
 264   start = i = 0;
 265   c = 1;
 266   while (c)
 267     {
 268       c = brace_gobbler (text, tlen, &i, brace_arg_separator);
 269 #if defined (SHELL)
 270       tem = substring (text, start, i);
 271 #else
 272       tem = (char *)xmalloc (1 + (i - start));
 273       strncpy (tem, &text[start], (i - start));
 274       tem[i- start] = '\0';
 275 #endif
 276
 277       partial = brace_expand (tem);
 278
 279       if (!result)
 280         result = partial;
 281       else
 282         {
 283           register int lr, lp, j;
 284
 285           lr = strvec_len (result);
 286           lp = strvec_len (partial);
 287
 288           result = strvec_resize (result, lp + lr + 1);
 289
 290           for (j = 0; j < lp; j++)
 291             result[lr + j] = partial[j];
 292
 293           result[lr + j] = (char *)NULL;
 294           free (partial);
 295         }
 296       free (tem);
 297       ADVANCE_CHAR (text, tlen, i);
 298       start = i;
 299     }
 300   return (result);
 301 }
 302
 303 #define ST_BAD  0
 304 #define ST_INT  1
 305 #define ST_CHAR 2
 306 #define ST_ZINT 3
 307
 308 static char **
 309 mkseq (start, end, incr, type, width)
 310      intmax_t start, end;
 311      int incr, type, width;
 312 {
 313   intmax_t n;
 314   int i;
 315   char **result, *t;
 316
 317   i = abs (end - start) + 1;
 318   result = strvec_create (i + 1);
 319
 320   if (incr == 0)
 321     incr = 1;
 322
 323   if (start > end && incr > 0)
 324     incr = -incr;
 325   else if (start < end && incr < 0)
 326     incr = -incr;
 327
 328   /* Make sure we go through the loop at least once, so {3..3} prints `3' */
 329   i = 0;
 330   n = start;
 331   do
 332     {
 333 #if defined (SHELL)
 334       QUIT;             /* XXX - memory leak here */
 335 #endif
 336       if (type == ST_INT)
 337         result[i++] = itos (n);
 338       else if (type == ST_ZINT)
 339         {
 340           int len, arg;
 341           arg = n;
 342           len = asprintf (&t, "%0*d", width, arg);
 343           result[i++] = t;
 344         }
 345       else
 346         {
 347           t = (char *)xmalloc (2);
 348           t[0] = n;
 349           t[1] = '\0';
 350           result[i++] = t;
 351         }
 352       n += incr;
 353       if ((incr < 0 && n < end) || (incr > 0 && n > end))
 354         break;
 355     }
 356   while (1);
 357
 358   result[i] = (char *)0;
 359   return (result);
 360 }
 361
 362 static char **
 363 expand_seqterm (text, tlen)
 364      char *text;
 365      size_t tlen;
 366 {
 367   char *t, *lhs, *rhs;
 368   int i, lhs_t, rhs_t, incr, lhs_l, rhs_l, width;
 369   intmax_t lhs_v, rhs_v;
 370   intmax_t tl, tr;
 371   char **result, *ep, *oep;
 372
 373   t = strstr (text, BRACE_SEQ_SPECIFIER);
 374   if (t == 0)
 375     return ((char **)NULL);
 376
 377   lhs_l = t - text;             /* index of start of BRACE_SEQ_SPECIFIER */
 378   lhs = substring (text, 0, lhs_l);
 379   rhs = substring (text, lhs_l + sizeof(BRACE_SEQ_SPECIFIER) - 1, tlen);
 380
 381   if (lhs[0] == 0 || rhs[0] == 0)
 382     {
 383       free (lhs);
 384       free (rhs);
 385       return ((char **)NULL);
 386     }
 387
 388   /* Now figure out whether LHS and RHS are integers or letters.  Both
 389      sides have to match. */
 390   lhs_t = (legal_number (lhs, &tl)) ? ST_INT :
 391                 ((ISALPHA (lhs[0]) && lhs[1] == 0) ?  ST_CHAR : ST_BAD);
 392
 393   /* Decide on rhs and whether or not it looks like the user specified
 394      an increment */
 395   ep = 0;
 396   if (ISDIGIT (rhs[0]) || ((rhs[0] == '+' || rhs[0] == '-') && ISDIGIT (rhs[1])))
 397     {
 398       rhs_t = ST_INT;
 399       tr = strtoimax (rhs, &ep, 10);
 400       if (ep && *ep != 0 && *ep != '.')
 401         rhs_t = ST_BAD;                 /* invalid */
 402     }
 403   else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.'))
 404     {
 405       rhs_t = ST_CHAR;
 406       ep = rhs + 1;
 407     }
 408   else
 409     {
 410       rhs_t = ST_BAD;
 411       ep = 0;
 412     }
 413
 414   incr = 1;
 415   if (rhs_t != ST_BAD)
 416     {
 417       oep = ep;
 418       if (ep && *ep == '.' && ep[1] == '.' && ep[2])
 419         incr = strtoimax (ep + 2, &ep, 10);
 420       if (*ep != 0)
 421         rhs_t = ST_BAD;                 /* invalid incr */
 422       tlen -= ep - oep;
 423     }
 424
 425   if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
 426     {
 427       free (lhs);
 428       free (rhs);
 429       return ((char **)NULL);
 430     }
 431
 432   /* OK, we have something.  It's either a sequence of integers, ascending
 433      or descending, or a sequence or letters, ditto.  Generate the sequence,
 434      put it into a string vector, and return it. */
 435
 436   if (lhs_t == ST_CHAR)
 437     {
 438       lhs_v = (unsigned char)lhs[0];
 439       rhs_v = (unsigned char)rhs[0];
 440       width = 1;
 441     }
 442   else
 443     {
 444       lhs_v = tl;               /* integer truncation */
 445       rhs_v = tr;
 446
 447       /* Decide whether or not the terms need zero-padding */
 448       rhs_l = tlen - lhs_l - sizeof (BRACE_SEQ_SPECIFIER) + 1;
 449       width = 0;
 450       if (lhs_l > 1 && lhs[0] == '0')
 451         width = lhs_l, lhs_t = ST_ZINT;
 452       if (lhs_l > 2 && lhs[0] == '-' && lhs[1] == '0')
 453         width = lhs_l, lhs_t = ST_ZINT;
 454       if (rhs_l > 1 && rhs[0] == '0' && width < rhs_l)
 455         width = rhs_l, lhs_t = ST_ZINT;
 456       if (rhs_l > 2 && rhs[0] == '-' && rhs[1] == '0' && width < rhs_l)
 457         width = rhs_l, lhs_t = ST_ZINT;
 458
 459       if (width < lhs_l && lhs_t == ST_ZINT)
 460         width = lhs_l;
 461       if (width < rhs_l && lhs_t == ST_ZINT)
 462         width = rhs_l;
 463     }
 464
 465   result = mkseq (lhs_v, rhs_v, incr, lhs_t, width);
 466
 467   free (lhs);
 468   free (rhs);
 469
 470   return (result);
 471 }
 472
 473 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
 474    index of the character matching SATISFY.  This understands about
 475    quoting.  Return the character that caused us to stop searching;
 476    this is either the same as SATISFY, or 0. */
 477 /* If SATISFY is `}', we are looking for a brace expression, so we
 478    should enforce the rules that govern valid brace expansions:
 479         1) to count as an arg separator, a comma or `..' has to be outside
 480            an inner set of braces.
 481 */
 482 static int
 483 brace_gobbler (text, tlen, indx, satisfy)
 484      char *text;
 485      size_t tlen;
 486      int *indx;
 487      int satisfy;
 488 {
 489   register int i, c, quoted, level, commas, pass_next;
 490 #if defined (SHELL)
 491   int si;
 492   char *t;
 493 #endif
 494   DECLARE_MBSTATE;
 495
 496   level = quoted = pass_next = 0;
 497 #if defined (CSH_BRACE_COMPAT)
 498   commas = 1;
 499 #else
 500   commas = (satisfy == '}') ? 0 : 1;
 501 #endif
 502
 503   i = *indx;
 504   while (c = text[i])
 505     {
 506       if (pass_next)
 507         {
 508           pass_next = 0;
 509           ADVANCE_CHAR (text, tlen, i);
 510           continue;
 511         }
 512
 513       /* A backslash escapes the next character.  This allows backslash to
 514          escape the quote character in a double-quoted string. */
 515       if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
 516         {
 517           pass_next = 1;
 518           i++;
 519           continue;
 520         }
 521
 522 #if defined (SHELL)
 523       /* If compiling for the shell, treat ${...} like \{...} */
 524       if (c == '$' && text[i+1] == '{' && quoted != '\'')               /* } */
 525         {
 526           pass_next = 1;
 527           i++;
 528           if (quoted == 0)
 529             level++;
 530           continue;
 531         }
 532 #endif
 533
 534       if (quoted)
 535         {
 536           if (c == quoted)
 537             quoted = 0;
 538           ADVANCE_CHAR (text, tlen, i);
 539           continue;
 540         }
 541
 542       if (c == '"' || c == '\'' || c == '`')
 543         {
 544           quoted = c;
 545           i++;
 546           continue;
 547         }
 548
 549 #if defined (SHELL)
 550       /* Pass new-style command and process substitutions through unchanged. */
 551       if ((c == '$' || c == '<' || c == '>') && text[i+1] == '(')                       /* ) */
 552         {
 553           si = i + 2;
 554           t = extract_command_subst (text, &si, 0);
 555           i = si;
 556           free (t);
 557           i++;
 558           continue;
 559         }
 560 #endif
 561
 562       if (c == satisfy && level == 0 && quoted == 0 && commas > 0)
 563         {
 564           /* We ignore an open brace surrounded by whitespace, and also
 565              an open brace followed immediately by a close brace preceded
 566              by whitespace.  */
 567           if (c == '{' &&
 568               ((!i || brace_whitespace (text[i - 1])) &&
 569                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 570             {
 571               i++;
 572               continue;
 573             }
 574
 575             break;
 576         }
 577
 578       if (c == '{')
 579         level++;
 580       else if (c == '}' && level)
 581         level--;
 582 #if !defined (CSH_BRACE_COMPAT)
 583       else if (satisfy == '}' && c == brace_arg_separator && level == 0)
 584         commas++;
 585       else if (satisfy == '}' && STREQN (text+i, BRACE_SEQ_SPECIFIER, 2) &&
 586                 text[i+2] != satisfy && level == 0)
 587         commas++;
 588 #endif
 589
 590       ADVANCE_CHAR (text, tlen, i);
 591     }
 592
 593   *indx = i;
 594   return (c);
 595 }
 596
 597 /* Return a new array of strings which is the result of appending each
 598    string in ARR2 to each string in ARR1.  The resultant array is
 599    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 600    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 601    is returned. */
 602 static char **
 603 array_concat (arr1, arr2)
 604      char **arr1, **arr2;
 605 {
 606   register int i, j, len, len1, len2;
 607   register char **result;
 608
 609   if (arr1 == 0)
 610     return (strvec_copy (arr2));
 611
 612   if (arr2 == 0)
 613     return (strvec_copy (arr1));
 614
 615   len1 = strvec_len (arr1);
 616   len2 = strvec_len (arr2);
 617
 618   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 619
 620   len = 0;
 621   for (i = 0; i < len1; i++)
 622     {
 623       int strlen_1 = strlen (arr1[i]);
 624
 625       for (j = 0; j < len2; j++)
 626         {
 627           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 628           strcpy (result[len], arr1[i]);
 629           strcpy (result[len] + strlen_1, arr2[j]);
 630           len++;
 631         }
 632       free (arr1[i]);
 633     }
 634   free (arr1);
 635
 636   result[len] = (char *)NULL;
 637   return (result);
 638 }
 639
 640 #if defined (TEST)
 641 #include <stdio.h>
 642
 643 fatal_error (format, arg1, arg2)
 644      char *format, *arg1, *arg2;
 645 {
 646   report_error (format, arg1, arg2);
 647   exit (1);
 648 }
 649
 650 report_error (format, arg1, arg2)
 651      char *format, *arg1, *arg2;
 652 {
 653   fprintf (stderr, format, arg1, arg2);
 654   fprintf (stderr, "\n");
 655 }
 656
 657 main ()
 658 {
 659   char example[256];
 660
 661   for (;;)
 662     {
 663       char **result;
 664       int i;
 665
 666       fprintf (stderr, "brace_expand> ");
 667
 668       if ((!fgets (example, 256, stdin)) ||
 669           (strncmp (example, "quit", 4) == 0))
 670         break;
 671
 672       if (strlen (example))
 673         example[strlen (example) - 1] = '\0';
 674
 675       result = brace_expand (example);
 676
 677       for (i = 0; result[i]; i++)
 678         printf ("%s\n", result[i]);
 679
 680       free_array (result);
 681     }
 682 }
 683 \f
 684 /*
 685  * Local variables:
 686  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 687  * end:
 688  */
 689
 690 #endif /* TEST */
 691 #endif /* BRACE_EXPANSION */