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((int, int, 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      int start, end, incr, type, width;
 311 {
 312   int n, i;
 313   char **result, *t;
 314
 315   n = abs (end - start) + 1;
 316   result = strvec_create (n + 1);
 317
 318   if (incr == 0)
 319     incr = 1;
 320
 321   if (start > end && incr > 0)
 322     incr = -incr;
 323   else if (start < end && incr < 0)
 324     incr = -incr;
 325
 326   /* Make sure we go through the loop at least once, so {3..3} prints `3' */
 327   i = 0;
 328   n = start;
 329   do
 330     {
 331 #if defined (SHELL)
 332       QUIT;             /* XXX - memory leak here */
 333 #endif
 334       if (type == ST_INT)
 335         result[i++] = itos (n);
 336       else if (type == ST_ZINT)
 337         {
 338           int len;
 339           len = asprintf (&t, "%0*d", width, n);
 340           result[i++] = t;
 341         }
 342       else
 343         {
 344           t = (char *)xmalloc (2);
 345           t[0] = n;
 346           t[1] = '\0';
 347           result[i++] = t;
 348         }
 349       n += incr;
 350       if ((incr < 0 && n < end) || (incr > 0 && n > end))
 351         break;
 352     }
 353   while (1);
 354
 355   result[i] = (char *)0;
 356   return (result);
 357 }
 358
 359 static char **
 360 expand_seqterm (text, tlen)
 361      char *text;
 362      size_t tlen;
 363 {
 364   char *t, *lhs, *rhs;
 365   int i, lhs_t, rhs_t, lhs_v, rhs_v, incr, lhs_l, rhs_l, width;
 366   intmax_t tl, tr;
 367   char **result, *ep;
 368
 369   t = strstr (text, BRACE_SEQ_SPECIFIER);
 370   if (t == 0)
 371     return ((char **)NULL);
 372
 373   lhs_l = t - text;             /* index of start of BRACE_SEQ_SPECIFIER */
 374   lhs = substring (text, 0, lhs_l);
 375   rhs = substring (text, lhs_l + sizeof(BRACE_SEQ_SPECIFIER) - 1, tlen);
 376
 377   if (lhs[0] == 0 || rhs[0] == 0)
 378     {
 379       free (lhs);
 380       free (rhs);
 381       return ((char **)NULL);
 382     }
 383
 384   /* Now figure out whether LHS and RHS are integers or letters.  Both
 385      sides have to match. */
 386   lhs_t = (legal_number (lhs, &tl)) ? ST_INT :
 387                 ((ISALPHA (lhs[0]) && lhs[1] == 0) ?  ST_CHAR : ST_BAD);
 388
 389   /* Decide on rhs and whether or not it looks like the user specified
 390      an increment */
 391   ep = 0;
 392   if (ISDIGIT (rhs[0]) || ((rhs[0] == '+' || rhs[0] == '-') && ISDIGIT (rhs[1])))
 393     {
 394       rhs_t = ST_INT;
 395       tr = strtoimax (rhs, &ep, 10);
 396       if (ep && *ep != 0 && *ep != '.')
 397         rhs_t = ST_BAD;                 /* invalid */
 398     }
 399   else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.'))
 400     {
 401       rhs_t = ST_CHAR;
 402       ep = rhs + 1;
 403     }
 404   else
 405     {
 406       rhs_t = ST_BAD;
 407       ep = 0;
 408     }
 409
 410   incr = 1;
 411   if (rhs_t != ST_BAD)
 412     {
 413       if (ep && *ep == '.' && ep[1] == '.' && ep[2])
 414         incr = strtoimax (ep + 2, &ep, 10);
 415       if (*ep != 0)
 416         rhs_t = ST_BAD;                 /* invalid incr */
 417     }
 418
 419   if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
 420     {
 421       free (lhs);
 422       free (rhs);
 423       return ((char **)NULL);
 424     }
 425
 426   /* OK, we have something.  It's either a sequence of integers, ascending
 427      or descending, or a sequence or letters, ditto.  Generate the sequence,
 428      put it into a string vector, and return it. */
 429
 430   if (lhs_t == ST_CHAR)
 431     {
 432       lhs_v = (unsigned char)lhs[0];
 433       rhs_v = (unsigned char)rhs[0];
 434       width = 1;
 435     }
 436   else
 437     {
 438       lhs_v = tl;               /* integer truncation */
 439       rhs_v = tr;
 440
 441       /* Decide whether or not the terms need zero-padding */
 442       rhs_l = tlen - lhs_l - sizeof (BRACE_SEQ_SPECIFIER) + 1;
 443       width = 0;
 444       if (lhs_l > 1 && lhs[0] == '0')
 445         width = lhs_l, lhs_t = ST_ZINT;
 446       if (lhs_l > 2 && lhs[0] == '-' && lhs[1] == '0')
 447         width = lhs_l, lhs_t = ST_ZINT;
 448       if (rhs_l > 1 && rhs[0] == '0' && width < rhs_l)
 449         width = rhs_l, lhs_t = ST_ZINT;
 450       if (rhs_l > 2 && rhs[0] == '-' && rhs[1] == '0' && width < rhs_l)
 451         width = rhs_l, lhs_t = ST_ZINT;
 452     }
 453
 454   result = mkseq (lhs_v, rhs_v, incr, lhs_t, width);
 455
 456   free (lhs);
 457   free (rhs);
 458
 459   return (result);
 460 }
 461
 462 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
 463    index of the character matching SATISFY.  This understands about
 464    quoting.  Return the character that caused us to stop searching;
 465    this is either the same as SATISFY, or 0. */
 466 /* If SATISFY is `}', we are looking for a brace expression, so we
 467    should enforce the rules that govern valid brace expansions:
 468         1) to count as an arg separator, a comma or `..' has to be outside
 469            an inner set of braces.
 470 */
 471 static int
 472 brace_gobbler (text, tlen, indx, satisfy)
 473      char *text;
 474      size_t tlen;
 475      int *indx;
 476      int satisfy;
 477 {
 478   register int i, c, quoted, level, commas, pass_next;
 479 #if defined (SHELL)
 480   int si;
 481   char *t;
 482 #endif
 483   DECLARE_MBSTATE;
 484
 485   level = quoted = pass_next = 0;
 486 #if defined (CSH_BRACE_COMPAT)
 487   commas = 1;
 488 #else
 489   commas = (satisfy == '}') ? 0 : 1;
 490 #endif
 491
 492   i = *indx;
 493   while (c = text[i])
 494     {
 495       if (pass_next)
 496         {
 497           pass_next = 0;
 498           ADVANCE_CHAR (text, tlen, i);
 499           continue;
 500         }
 501
 502       /* A backslash escapes the next character.  This allows backslash to
 503          escape the quote character in a double-quoted string. */
 504       if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
 505         {
 506           pass_next = 1;
 507           i++;
 508           continue;
 509         }
 510
 511 #if defined (SHELL)
 512       /* If compiling for the shell, treat ${...} like \{...} */
 513       if (c == '$' && text[i+1] == '{' && quoted != '\'')               /* } */
 514         {
 515           pass_next = 1;
 516           i++;
 517           if (quoted == 0)
 518             level++;
 519           continue;
 520         }
 521 #endif
 522
 523       if (quoted)
 524         {
 525           if (c == quoted)
 526             quoted = 0;
 527           ADVANCE_CHAR (text, tlen, i);
 528           continue;
 529         }
 530
 531       if (c == '"' || c == '\'' || c == '`')
 532         {
 533           quoted = c;
 534           i++;
 535           continue;
 536         }
 537
 538 #if defined (SHELL)
 539       /* Pass new-style command and process substitutions through unchanged. */
 540       if ((c == '$' || c == '<' || c == '>') && text[i+1] == '(')                       /* ) */
 541         {
 542           si = i + 2;
 543           t = extract_command_subst (text, &si, 0);
 544           i = si;
 545           free (t);
 546           i++;
 547           continue;
 548         }
 549 #endif
 550
 551       if (c == satisfy && level == 0 && quoted == 0 && commas > 0)
 552         {
 553           /* We ignore an open brace surrounded by whitespace, and also
 554              an open brace followed immediately by a close brace preceded
 555              by whitespace.  */
 556           if (c == '{' &&
 557               ((!i || brace_whitespace (text[i - 1])) &&
 558                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 559             {
 560               i++;
 561               continue;
 562             }
 563
 564             break;
 565         }
 566
 567       if (c == '{')
 568         level++;
 569       else if (c == '}' && level)
 570         level--;
 571 #if !defined (CSH_BRACE_COMPAT)
 572       else if (satisfy == '}' && c == brace_arg_separator && level == 0)
 573         commas++;
 574       else if (satisfy == '}' && STREQN (text+i, BRACE_SEQ_SPECIFIER, 2) &&
 575                 text[i+2] != satisfy && level == 0)
 576         commas++;
 577 #endif
 578
 579       ADVANCE_CHAR (text, tlen, i);
 580     }
 581
 582   *indx = i;
 583   return (c);
 584 }
 585
 586 /* Return a new array of strings which is the result of appending each
 587    string in ARR2 to each string in ARR1.  The resultant array is
 588    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 589    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 590    is returned. */
 591 static char **
 592 array_concat (arr1, arr2)
 593      char **arr1, **arr2;
 594 {
 595   register int i, j, len, len1, len2;
 596   register char **result;
 597
 598   if (arr1 == 0)
 599     return (strvec_copy (arr2));
 600
 601   if (arr2 == 0)
 602     return (strvec_copy (arr1));
 603
 604   len1 = strvec_len (arr1);
 605   len2 = strvec_len (arr2);
 606
 607   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 608
 609   len = 0;
 610   for (i = 0; i < len1; i++)
 611     {
 612       int strlen_1 = strlen (arr1[i]);
 613
 614       for (j = 0; j < len2; j++)
 615         {
 616           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 617           strcpy (result[len], arr1[i]);
 618           strcpy (result[len] + strlen_1, arr2[j]);
 619           len++;
 620         }
 621       free (arr1[i]);
 622     }
 623   free (arr1);
 624
 625   result[len] = (char *)NULL;
 626   return (result);
 627 }
 628
 629 #if defined (TEST)
 630 #include <stdio.h>
 631
 632 fatal_error (format, arg1, arg2)
 633      char *format, *arg1, *arg2;
 634 {
 635   report_error (format, arg1, arg2);
 636   exit (1);
 637 }
 638
 639 report_error (format, arg1, arg2)
 640      char *format, *arg1, *arg2;
 641 {
 642   fprintf (stderr, format, arg1, arg2);
 643   fprintf (stderr, "\n");
 644 }
 645
 646 main ()
 647 {
 648   char example[256];
 649
 650   for (;;)
 651     {
 652       char **result;
 653       int i;
 654
 655       fprintf (stderr, "brace_expand> ");
 656
 657       if ((!fgets (example, 256, stdin)) ||
 658           (strncmp (example, "quit", 4) == 0))
 659         break;
 660
 661       if (strlen (example))
 662         example[strlen (example) - 1] = '\0';
 663
 664       result = brace_expand (example);
 665
 666       for (i = 0; result[i]; i++)
 667         printf ("%s\n", result[i]);
 668
 669       free_array (result);
 670     }
 671 }
 672 \f
 673 /*
 674  * Local variables:
 675  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 676  * end:
 677  */
 678
 679 #endif /* TEST */
 680 #endif /* BRACE_EXPANSION */