braces.c

   1 /* braces.c -- code for doing word expansion in curly braces. */
   2
   3 /* Copyright (C) 1987-2003 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 it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    Bash is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash; see the file COPYING.  If not, write to the Free
  19    Software Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
  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 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));
  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 /* Return an array of strings; the brace expansion of TEXT. */
  75 char **
  76 brace_expand (text)
  77      char *text;
  78 {
  79   register int start;
  80   size_t tlen;
  81   char *preamble, *postamble, *amble;
  82   size_t alen;
  83   char **tack, **result;
  84   int i, j, c;
  85
  86   DECLARE_MBSTATE;
  87
  88   /* Find the text of the preamble. */
  89   tlen = strlen (text);
  90   i = 0;
  91   c = brace_gobbler (text, tlen, &i, '{');
  92
  93   preamble = (char *)xmalloc (i + 1);
  94   strncpy (preamble, text, i);
  95   preamble[i] = '\0';
  96
  97   result = (char **)xmalloc (2 * sizeof (char *));
  98   result[0] = preamble;
  99   result[1] = (char *)NULL;
 100
 101   /* Special case.  If we never found an exciting character, then
 102      the preamble is all of the text, so just return that. */
 103   if (c != '{')
 104     return (result);
 105
 106   /* Find the amble.  This is the stuff inside this set of braces. */
 107   start = ++i;
 108   c = brace_gobbler (text, tlen, &i, '}');
 109
 110   /* What if there isn't a matching close brace? */
 111   if (c == 0)
 112     {
 113 #if defined (NOTDEF)
 114       /* Well, if we found an unquoted BRACE_ARG_SEPARATOR between START
 115          and I, then this should be an error.  Otherwise, it isn't. */
 116       j = start;
 117       while (j < i)
 118         {
 119           if (text[j] == '\\')
 120             {
 121               j++;
 122               ADVANCE_CHAR (text, tlen, j);
 123               continue;
 124             }
 125
 126           if (text[j] == brace_arg_separator)
 127             {   /* { */
 128               strvec_dispose (result);
 129               report_error ("no closing `%c' in %s", '}', text);
 130               throw_to_top_level ();
 131             }
 132           ADVANCE_CHAR (text, tlen, j);
 133         }
 134 #endif
 135       free (preamble);          /* Same as result[0]; see initialization. */
 136       result[0] = savestring (text);
 137       return (result);
 138     }
 139
 140 #if defined (SHELL)
 141   amble = substring (text, start, i);
 142   alen = i - start;
 143 #else
 144   amble = (char *)xmalloc (1 + (i - start));
 145   strncpy (amble, &text[start], (i - start));
 146   alen = i - start;
 147   amble[alen] = '\0';
 148 #endif
 149
 150 #if defined (SHELL)
 151   INITIALIZE_MBSTATE;
 152
 153   /* If the amble does not contain an unquoted BRACE_ARG_SEPARATOR, then
 154      just return without doing any expansion.  */
 155   j = 0;
 156   while (amble[j])
 157     {
 158       if (amble[j] == '\\')
 159         {
 160           j++;
 161           ADVANCE_CHAR (amble, alen, j);
 162           continue;
 163         }
 164
 165       if (amble[j] == brace_arg_separator)
 166         break;
 167
 168       ADVANCE_CHAR (amble, alen, j);
 169     }
 170
 171   if (amble[j] == 0)
 172     {
 173       tack = expand_seqterm (amble, alen);
 174       if (tack)
 175         goto add_tack;
 176       else
 177         {
 178           free (amble);
 179           free (preamble);
 180           result[0] = savestring (text);
 181           return (result);
 182         }
 183     }
 184 #endif /* SHELL */
 185
 186   tack = expand_amble (amble, alen, 0);
 187 add_tack:
 188   result = array_concat (result, tack);
 189   free (amble);
 190   strvec_dispose (tack);
 191
 192   postamble = text + i + 1;
 193
 194   tack = brace_expand (postamble);
 195   result = array_concat (result, tack);
 196   strvec_dispose (tack);
 197
 198   return (result);
 199 }
 200
 201 /* Expand the text found inside of braces.  We simply try to split the
 202    text at BRACE_ARG_SEPARATORs into separate strings.  We then brace
 203    expand each slot which needs it, until there are no more slots which
 204    need it. */
 205 static char **
 206 expand_amble (text, tlen, flags)
 207      char *text;
 208      size_t tlen;
 209      int flags;
 210 {
 211   char **result, **partial;
 212   char *tem;
 213   int start, i, c;
 214
 215   DECLARE_MBSTATE;
 216
 217   result = (char **)NULL;
 218
 219   start = i = 0;
 220   c = 1;
 221   while (c)
 222     {
 223       c = brace_gobbler (text, tlen, &i, brace_arg_separator);
 224 #if defined (SHELL)
 225       tem = substring (text, start, i);
 226 #else
 227       tem = (char *)xmalloc (1 + (i - start));
 228       strncpy (tem, &text[start], (i - start));
 229       tem[i- start] = '\0';
 230 #endif
 231
 232       partial = brace_expand (tem);
 233
 234       if (!result)
 235         result = partial;
 236       else
 237         {
 238           register int lr, lp, j;
 239
 240           lr = strvec_len (result);
 241           lp = strvec_len (partial);
 242
 243           result = strvec_resize (result, lp + lr + 1);
 244
 245           for (j = 0; j < lp; j++)
 246             result[lr + j] = partial[j];
 247
 248           result[lr + j] = (char *)NULL;
 249           free (partial);
 250         }
 251       free (tem);
 252       ADVANCE_CHAR (text, tlen, i);
 253       start = i;
 254     }
 255   return (result);
 256 }
 257
 258 #define ST_BAD  0
 259 #define ST_INT  1
 260 #define ST_CHAR 2
 261
 262 static char **
 263 mkseq (start, end, type)
 264      int start, end, type;
 265 {
 266   int n, incr, i;
 267   char **result, *t;
 268
 269   n = abs (end - start) + 1;
 270   result = strvec_create (n + 1);
 271
 272   incr = (start < end) ? 1 : -1;
 273
 274   /* Make sure we go through the loop at least once, so {3..3} prints `3' */
 275   i = 0;
 276   n = start;
 277   do
 278     {
 279       if (type == ST_INT)
 280         result[i++] = itos (n);
 281       else
 282         {
 283           t = (char *)xmalloc (2);
 284           t[0] = n;
 285           t[1] = '\0';
 286           result[i++] = t;
 287         }
 288       if (n == end)
 289         break;
 290       n += incr;
 291     }
 292   while (1);
 293
 294   result[i] = (char *)0;
 295   return (result);
 296 }
 297
 298 static char **
 299 expand_seqterm (text, tlen)
 300      char *text;
 301      size_t tlen;
 302 {
 303   char *t, *lhs, *rhs;
 304   int i, lhs_t, rhs_t, lhs_v, rhs_v;
 305   intmax_t tl, tr;
 306   char **result;
 307
 308   t = strstr (text, BRACE_SEQ_SPECIFIER);
 309   if (t == 0)
 310     return ((char **)NULL);
 311
 312   i = t - text;         /* index of start of BRACE_SEQ_SPECIFIER */
 313   lhs = substring (text, 0, i);
 314   rhs = substring (text, i + sizeof(BRACE_SEQ_SPECIFIER) - 1, tlen);
 315
 316   if (lhs[0] == 0 || rhs[0] == 0)
 317     {
 318       free (lhs);
 319       free (rhs);
 320       return ((char **)NULL);
 321     }
 322
 323   /* Now figure out whether LHS and RHS are integers or letters.  Both
 324      sides have to match. */
 325   lhs_t = (legal_number (lhs, &tl)) ? ST_INT :
 326                 ((ISALPHA (lhs[0]) && lhs[1] == 0) ?  ST_CHAR : ST_BAD);
 327   rhs_t = (legal_number (rhs, &tr)) ? ST_INT :
 328                 ((ISALPHA (rhs[0]) && rhs[1] == 0) ?  ST_CHAR : ST_BAD);
 329
 330   if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
 331     {
 332       free (lhs);
 333       free (rhs);
 334       return ((char **)NULL);
 335     }
 336
 337   /* OK, we have something.  It's either a sequence of integers, ascending
 338      or descending, or a sequence or letters, ditto.  Generate the sequence,
 339      put it into a string vector, and return it. */
 340
 341   if (lhs_t == ST_CHAR)
 342     {
 343       lhs_v = lhs[0];
 344       rhs_v = rhs[0];
 345     }
 346   else
 347     {
 348       lhs_v = tl;               /* integer truncation */
 349       rhs_v = tr;
 350     }
 351
 352   result = mkseq (lhs_v, rhs_v, lhs_t);
 353
 354   free (lhs);
 355   free (rhs);
 356
 357   return (result);
 358 }
 359
 360 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
 361    index of the character matching SATISFY.  This understands about
 362    quoting.  Return the character that caused us to stop searching;
 363    this is either the same as SATISFY, or 0. */
 364 static int
 365 brace_gobbler (text, tlen, indx, satisfy)
 366      char *text;
 367      size_t tlen;
 368      int *indx;
 369      int satisfy;
 370 {
 371   register int i, c, quoted, level, pass_next;
 372 #if defined (SHELL)
 373   int si;
 374   char *t;
 375 #endif
 376   DECLARE_MBSTATE;
 377
 378   level = quoted = pass_next = 0;
 379
 380   i = *indx;
 381   while (c = text[i])
 382     {
 383       if (pass_next)
 384         {
 385           pass_next = 0;
 386           ADVANCE_CHAR (text, tlen, i);
 387           continue;
 388         }
 389
 390       /* A backslash escapes the next character.  This allows backslash to
 391          escape the quote character in a double-quoted string. */
 392       if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
 393         {
 394           pass_next = 1;
 395           i++;
 396           continue;
 397         }
 398
 399 #if defined (SHELL)
 400       /* If compiling for the shell, treat ${...} like \{...} */
 401       if (c == '$' && text[i+1] == '{' && quoted != '\'')               /* } */
 402         {
 403           pass_next = 1;
 404           i++;
 405           continue;
 406         }
 407 #endif
 408
 409       if (quoted)
 410         {
 411           if (c == quoted)
 412             quoted = 0;
 413           ADVANCE_CHAR (text, tlen, i);
 414           continue;
 415         }
 416
 417       if (c == '"' || c == '\'' || c == '`')
 418         {
 419           quoted = c;
 420           i++;
 421           continue;
 422         }
 423
 424 #if defined (SHELL)
 425       /* Pass new-style command substitutions through unchanged. */
 426       if (c == '$' && text[i+1] == '(')                 /* ) */
 427         {
 428           si = i + 2;
 429           t = extract_command_subst (text, &si);
 430           i = si;
 431           free (t);
 432           i++;
 433           continue;
 434         }
 435 #endif
 436
 437       if (c == satisfy && level == 0 && quoted == 0)
 438         {
 439           /* We ignore an open brace surrounded by whitespace, and also
 440              an open brace followed immediately by a close brace preceded
 441              by whitespace.  */
 442           if (c == '{' &&
 443               ((!i || brace_whitespace (text[i - 1])) &&
 444                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 445             {
 446               i++;
 447               continue;
 448             }
 449
 450             break;
 451         }
 452
 453       if (c == '{')
 454         level++;
 455       else if (c == '}' && level)
 456         level--;
 457
 458       ADVANCE_CHAR (text, tlen, i);
 459     }
 460
 461   *indx = i;
 462   return (c);
 463 }
 464
 465 /* Return a new array of strings which is the result of appending each
 466    string in ARR2 to each string in ARR1.  The resultant array is
 467    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 468    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 469    is returned. */
 470 static char **
 471 array_concat (arr1, arr2)
 472      char **arr1, **arr2;
 473 {
 474   register int i, j, len, len1, len2;
 475   register char **result;
 476
 477   if (arr1 == 0)
 478     return (strvec_copy (arr2));
 479
 480   if (arr2 == 0)
 481     return (strvec_copy (arr1));
 482
 483   len1 = strvec_len (arr1);
 484   len2 = strvec_len (arr2);
 485
 486   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 487
 488   len = 0;
 489   for (i = 0; i < len1; i++)
 490     {
 491       int strlen_1 = strlen (arr1[i]);
 492
 493       for (j = 0; j < len2; j++)
 494         {
 495           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 496           strcpy (result[len], arr1[i]);
 497           strcpy (result[len] + strlen_1, arr2[j]);
 498           len++;
 499         }
 500       free (arr1[i]);
 501     }
 502   free (arr1);
 503
 504   result[len] = (char *)NULL;
 505   return (result);
 506 }
 507
 508 #if defined (TEST)
 509 #include <stdio.h>
 510
 511 fatal_error (format, arg1, arg2)
 512      char *format, *arg1, *arg2;
 513 {
 514   report_error (format, arg1, arg2);
 515   exit (1);
 516 }
 517
 518 report_error (format, arg1, arg2)
 519      char *format, *arg1, *arg2;
 520 {
 521   fprintf (stderr, format, arg1, arg2);
 522   fprintf (stderr, "\n");
 523 }
 524
 525 main ()
 526 {
 527   char example[256];
 528
 529   for (;;)
 530     {
 531       char **result;
 532       int i;
 533
 534       fprintf (stderr, "brace_expand> ");
 535
 536       if ((!fgets (example, 256, stdin)) ||
 537           (strncmp (example, "quit", 4) == 0))
 538         break;
 539
 540       if (strlen (example))
 541         example[strlen (example) - 1] = '\0';
 542
 543       result = brace_expand (example);
 544
 545       for (i = 0; result[i]; i++)
 546         printf ("%s\n", result[i]);
 547
 548       free_array (result);
 549     }
 550 }
 551 \f
 552 /*
 553  * Local variables:
 554  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 555  * end:
 556  */
 557
 558 #endif /* TEST */
 559 #endif /* BRACE_EXPANSION */