braces.c~

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