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, *oep;
 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       oep = ep;
 414       if (ep && *ep == '.' && ep[1] == '.' && ep[2])
 415         incr = strtoimax (ep + 2, &ep, 10);
 416       if (*ep != 0)
 417         rhs_t = ST_BAD;                 /* invalid incr */
 418       tlen -= ep - oep;
 419     }
 420
 421   if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
 422     {
 423       free (lhs);
 424       free (rhs);
 425       return ((char **)NULL);
 426     }
 427
 428   /* OK, we have something.  It's either a sequence of integers, ascending
 429      or descending, or a sequence or letters, ditto.  Generate the sequence,
 430      put it into a string vector, and return it. */
 431
 432   if (lhs_t == ST_CHAR)
 433     {
 434       lhs_v = (unsigned char)lhs[0];
 435       rhs_v = (unsigned char)rhs[0];
 436       width = 1;
 437     }
 438   else
 439     {
 440       lhs_v = tl;               /* integer truncation */
 441       rhs_v = tr;
 442
 443       /* Decide whether or not the terms need zero-padding */
 444       rhs_l = tlen - lhs_l - sizeof (BRACE_SEQ_SPECIFIER) + 1;
 445       width = 0;
 446       if (lhs_l > 1 && lhs[0] == '0')
 447         width = lhs_l, lhs_t = ST_ZINT;
 448       if (lhs_l > 2 && lhs[0] == '-' && lhs[1] == '0')
 449         width = lhs_l, lhs_t = ST_ZINT;
 450       if (rhs_l > 1 && rhs[0] == '0' && width < rhs_l)
 451         width = rhs_l, lhs_t = ST_ZINT;
 452       if (rhs_l > 2 && rhs[0] == '-' && rhs[1] == '0' && width < rhs_l)
 453         width = rhs_l, lhs_t = ST_ZINT;
 454
 455       if (width < lhs_l && lhs_t == ST_ZINT)
 456         width = lhs_l;
 457       if (width < rhs_l && lhs_t == ST_ZINT)
 458         width = rhs_l;
 459     }
 460
 461   result = mkseq (lhs_v, rhs_v, incr, lhs_t, width);
 462
 463   free (lhs);
 464   free (rhs);
 465
 466   return (result);
 467 }
 468
 469 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
 470    index of the character matching SATISFY.  This understands about
 471    quoting.  Return the character that caused us to stop searching;
 472    this is either the same as SATISFY, or 0. */
 473 /* If SATISFY is `}', we are looking for a brace expression, so we
 474    should enforce the rules that govern valid brace expansions:
 475         1) to count as an arg separator, a comma or `..' has to be outside
 476            an inner set of braces.
 477 */
 478 static int
 479 brace_gobbler (text, tlen, indx, satisfy)
 480      char *text;
 481      size_t tlen;
 482      int *indx;
 483      int satisfy;
 484 {
 485   register int i, c, quoted, level, commas, pass_next;
 486 #if defined (SHELL)
 487   int si;
 488   char *t;
 489 #endif
 490   DECLARE_MBSTATE;
 491
 492   level = quoted = pass_next = 0;
 493 #if defined (CSH_BRACE_COMPAT)
 494   commas = 1;
 495 #else
 496   commas = (satisfy == '}') ? 0 : 1;
 497 #endif
 498
 499   i = *indx;
 500   while (c = text[i])
 501     {
 502       if (pass_next)
 503         {
 504           pass_next = 0;
 505           ADVANCE_CHAR (text, tlen, i);
 506           continue;
 507         }
 508
 509       /* A backslash escapes the next character.  This allows backslash to
 510          escape the quote character in a double-quoted string. */
 511       if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
 512         {
 513           pass_next = 1;
 514           i++;
 515           continue;
 516         }
 517
 518 #if defined (SHELL)
 519       /* If compiling for the shell, treat ${...} like \{...} */
 520       if (c == '$' && text[i+1] == '{' && quoted != '\'')               /* } */
 521         {
 522           pass_next = 1;
 523           i++;
 524           if (quoted == 0)
 525             level++;
 526           continue;
 527         }
 528 #endif
 529
 530       if (quoted)
 531         {
 532           if (c == quoted)
 533             quoted = 0;
 534           ADVANCE_CHAR (text, tlen, i);
 535           continue;
 536         }
 537
 538       if (c == '"' || c == '\'' || c == '`')
 539         {
 540           quoted = c;
 541           i++;
 542           continue;
 543         }
 544
 545 #if defined (SHELL)
 546       /* Pass new-style command and process substitutions through unchanged. */
 547       if ((c == '$' || c == '<' || c == '>') && text[i+1] == '(')                       /* ) */
 548         {
 549           si = i + 2;
 550           t = extract_command_subst (text, &si, 0);
 551           i = si;
 552           free (t);
 553           i++;
 554           continue;
 555         }
 556 #endif
 557
 558       if (c == satisfy && level == 0 && quoted == 0 && commas > 0)
 559         {
 560           /* We ignore an open brace surrounded by whitespace, and also
 561              an open brace followed immediately by a close brace preceded
 562              by whitespace.  */
 563           if (c == '{' &&
 564               ((!i || brace_whitespace (text[i - 1])) &&
 565                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 566             {
 567               i++;
 568               continue;
 569             }
 570
 571             break;
 572         }
 573
 574       if (c == '{')
 575         level++;
 576       else if (c == '}' && level)
 577         level--;
 578 #if !defined (CSH_BRACE_COMPAT)
 579       else if (satisfy == '}' && c == brace_arg_separator && level == 0)
 580         commas++;
 581       else if (satisfy == '}' && STREQN (text+i, BRACE_SEQ_SPECIFIER, 2) &&
 582                 text[i+2] != satisfy && level == 0)
 583         commas++;
 584 #endif
 585
 586       ADVANCE_CHAR (text, tlen, i);
 587     }
 588
 589   *indx = i;
 590   return (c);
 591 }
 592
 593 /* Return a new array of strings which is the result of appending each
 594    string in ARR2 to each string in ARR1.  The resultant array is
 595    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 596    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 597    is returned. */
 598 static char **
 599 array_concat (arr1, arr2)
 600      char **arr1, **arr2;
 601 {
 602   register int i, j, len, len1, len2;
 603   register char **result;
 604
 605   if (arr1 == 0)
 606     return (strvec_copy (arr2));
 607
 608   if (arr2 == 0)
 609     return (strvec_copy (arr1));
 610
 611   len1 = strvec_len (arr1);
 612   len2 = strvec_len (arr2);
 613
 614   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 615
 616   len = 0;
 617   for (i = 0; i < len1; i++)
 618     {
 619       int strlen_1 = strlen (arr1[i]);
 620
 621       for (j = 0; j < len2; j++)
 622         {
 623           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 624           strcpy (result[len], arr1[i]);
 625           strcpy (result[len] + strlen_1, arr2[j]);
 626           len++;
 627         }
 628       free (arr1[i]);
 629     }
 630   free (arr1);
 631
 632   result[len] = (char *)NULL;
 633   return (result);
 634 }
 635
 636 #if defined (TEST)
 637 #include <stdio.h>
 638
 639 fatal_error (format, arg1, arg2)
 640      char *format, *arg1, *arg2;
 641 {
 642   report_error (format, arg1, arg2);
 643   exit (1);
 644 }
 645
 646 report_error (format, arg1, arg2)
 647      char *format, *arg1, *arg2;
 648 {
 649   fprintf (stderr, format, arg1, arg2);
 650   fprintf (stderr, "\n");
 651 }
 652
 653 main ()
 654 {
 655   char example[256];
 656
 657   for (;;)
 658     {
 659       char **result;
 660       int i;
 661
 662       fprintf (stderr, "brace_expand> ");
 663
 664       if ((!fgets (example, 256, stdin)) ||
 665           (strncmp (example, "quit", 4) == 0))
 666         break;
 667
 668       if (strlen (example))
 669         example[strlen (example) - 1] = '\0';
 670
 671       result = brace_expand (example);
 672
 673       for (i = 0; result[i]; i++)
 674         printf ("%s\n", result[i]);
 675
 676       free_array (result);
 677     }
 678 }
 679 \f
 680 /*
 681  * Local variables:
 682  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 683  * end:
 684  */
 685
 686 #endif /* TEST */
 687 #endif /* BRACE_EXPANSION */