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 = (unsigned char)lhs[0];
 344       rhs_v = (unsigned char)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           level++;
 406           continue;
 407         }
 408 #endif
 409
 410       if (quoted)
 411         {
 412           if (c == quoted)
 413             quoted = 0;
 414           ADVANCE_CHAR (text, tlen, i);
 415           continue;
 416         }
 417
 418       if (c == '"' || c == '\'' || c == '`')
 419         {
 420           quoted = c;
 421           i++;
 422           continue;
 423         }
 424
 425 #if defined (SHELL)
 426       /* Pass new-style command substitutions through unchanged. */
 427       if (c == '$' && text[i+1] == '(')                 /* ) */
 428         {
 429           si = i + 2;
 430           t = extract_command_subst (text, &si);
 431           i = si;
 432           free (t);
 433           i++;
 434           continue;
 435         }
 436 #endif
 437
 438       if (c == satisfy && level == 0 && quoted == 0)
 439         {
 440           /* We ignore an open brace surrounded by whitespace, and also
 441              an open brace followed immediately by a close brace preceded
 442              by whitespace.  */
 443           if (c == '{' &&
 444               ((!i || brace_whitespace (text[i - 1])) &&
 445                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 446             {
 447               i++;
 448               continue;
 449             }
 450
 451             break;
 452         }
 453
 454       if (c == '{')
 455         level++;
 456       else if (c == '}' && level)
 457         level--;
 458
 459       ADVANCE_CHAR (text, tlen, i);
 460     }
 461
 462   *indx = i;
 463   return (c);
 464 }
 465
 466 /* Return a new array of strings which is the result of appending each
 467    string in ARR2 to each string in ARR1.  The resultant array is
 468    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 469    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 470    is returned. */
 471 static char **
 472 array_concat (arr1, arr2)
 473      char **arr1, **arr2;
 474 {
 475   register int i, j, len, len1, len2;
 476   register char **result;
 477
 478   if (arr1 == 0)
 479     return (strvec_copy (arr2));
 480
 481   if (arr2 == 0)
 482     return (strvec_copy (arr1));
 483
 484   len1 = strvec_len (arr1);
 485   len2 = strvec_len (arr2);
 486
 487   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 488
 489   len = 0;
 490   for (i = 0; i < len1; i++)
 491     {
 492       int strlen_1 = strlen (arr1[i]);
 493
 494       for (j = 0; j < len2; j++)
 495         {
 496           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 497           strcpy (result[len], arr1[i]);
 498           strcpy (result[len] + strlen_1, arr2[j]);
 499           len++;
 500         }
 501       free (arr1[i]);
 502     }
 503   free (arr1);
 504
 505   result[len] = (char *)NULL;
 506   return (result);
 507 }
 508
 509 #if defined (TEST)
 510 #include <stdio.h>
 511
 512 fatal_error (format, arg1, arg2)
 513      char *format, *arg1, *arg2;
 514 {
 515   report_error (format, arg1, arg2);
 516   exit (1);
 517 }
 518
 519 report_error (format, arg1, arg2)
 520      char *format, *arg1, *arg2;
 521 {
 522   fprintf (stderr, format, arg1, arg2);
 523   fprintf (stderr, "\n");
 524 }
 525
 526 main ()
 527 {
 528   char example[256];
 529
 530   for (;;)
 531     {
 532       char **result;
 533       int i;
 534
 535       fprintf (stderr, "brace_expand> ");
 536
 537       if ((!fgets (example, 256, stdin)) ||
 538           (strncmp (example, "quit", 4) == 0))
 539         break;
 540
 541       if (strlen (example))
 542         example[strlen (example) - 1] = '\0';
 543
 544       result = brace_expand (example);
 545
 546       for (i = 0; result[i]; i++)
 547         printf ("%s\n", result[i]);
 548
 549       free_array (result);
 550     }
 551 }
 552 \f
 553 /*
 554  * Local variables:
 555  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 556  * end:
 557  */
 558
 559 #endif /* TEST */
 560 #endif /* BRACE_EXPANSION */