braces.c

   1 /* braces.c -- code for doing word expansion in curly braces. */
   2
   3 /* Copyright (C) 1987-2012 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 <errno.h>
  35
  36 #include "bashansi.h"
  37 #include "bashintl.h"
  38
  39 #if defined (SHELL)
  40 #  include "shell.h"
  41 #else
  42 #  if defined (TEST)
  43 typedef char *WORD_DESC;
  44 typedef char **WORD_LIST;
  45 #define _(X)    X
  46 #  endif /* TEST */
  47 #endif /* SHELL */
  48
  49 #include "typemax.h"            /* INTMAX_MIN, INTMAX_MAX */
  50 #include "general.h"
  51 #include "shmbutil.h"
  52 #include "chartypes.h"
  53
  54 #ifndef errno
  55 extern int errno;
  56 #endif
  57
  58 #define brace_whitespace(c) (!(c) || (c) == ' ' || (c) == '\t' || (c) == '\n')
  59
  60 #define BRACE_SEQ_SPECIFIER     ".."
  61
  62 extern int asprintf __P((char **, const char *, ...)) __attribute__((__format__ (printf, 2, 3)));
  63
  64 extern int last_command_exit_value;
  65
  66 /* Basic idea:
  67
  68    Segregate the text into 3 sections: preamble (stuff before an open brace),
  69    postamble (stuff after the matching close brace) and amble (stuff after
  70    preamble, and before postamble).  Expand amble, and then tack on the
  71    expansions to preamble.  Expand postamble, and tack on the expansions to
  72    the result so far.
  73  */
  74
  75 /* The character which is used to separate arguments. */
  76 static const int brace_arg_separator = ',';
  77
  78 #if defined (__P)
  79 static int brace_gobbler __P((char *, size_t, int *, int));
  80 static char **expand_amble __P((char *, size_t, int));
  81 static char **expand_seqterm __P((char *, size_t));
  82 static char **mkseq __P((intmax_t, intmax_t, intmax_t, int, int));
  83 static char **array_concat __P((char **, char **));
  84 #else
  85 static int brace_gobbler ();
  86 static char **expand_amble ();
  87 static char **expand_seqterm ();
  88 static char **mkseq();
  89 static char **array_concat ();
  90 #endif
  91
  92 #if 0
  93 static void
  94 dump_result (a)
  95      char **a;
  96 {
  97   int i;
  98
  99   for (i = 0; a[i]; i++)
 100     printf ("dump_result: a[%d] = -%s-\n", i, a[i]);
 101 }
 102 #endif
 103
 104 /* Return an array of strings; the brace expansion of TEXT. */
 105 char **
 106 brace_expand (text)
 107      char *text;
 108 {
 109   register int start;
 110   size_t tlen;
 111   char *preamble, *postamble, *amble;
 112   size_t alen;
 113   char **tack, **result;
 114   int i, j, c, c1;
 115
 116   DECLARE_MBSTATE;
 117
 118   /* Find the text of the preamble. */
 119   tlen = strlen (text);
 120   i = 0;
 121 #if defined (CSH_BRACE_COMPAT)
 122   c = brace_gobbler (text, tlen, &i, '{');      /* } */
 123 #else
 124   /* Make sure that when we exit this loop, c == 0 or text[i] begins a
 125      valid brace expansion sequence. */
 126   do
 127     {
 128       c = brace_gobbler (text, tlen, &i, '{');  /* } */
 129       c1 = c;
 130       /* Verify that c begins a valid brace expansion word.  If it doesn't, we
 131          go on.  Loop stops when there are no more open braces in the word. */
 132       if (c)
 133         {
 134           start = j = i + 1;    /* { */
 135           c = brace_gobbler (text, tlen, &j, '}');
 136           if (c == 0)           /* it's not */
 137             {
 138               i++;
 139               c = c1;
 140               continue;
 141             }
 142           else                  /* it is */
 143             {
 144               c = c1;
 145               break;
 146             }
 147         }
 148       else
 149         break;
 150     }
 151   while (c);
 152 #endif /* !CSH_BRACE_COMPAT */
 153
 154   preamble = (char *)xmalloc (i + 1);
 155   if (i > 0)
 156     strncpy (preamble, text, i);
 157   preamble[i] = '\0';
 158
 159   result = (char **)xmalloc (2 * sizeof (char *));
 160   result[0] = preamble;
 161   result[1] = (char *)NULL;
 162
 163   /* Special case.  If we never found an exciting character, then
 164      the preamble is all of the text, so just return that. */
 165   if (c != '{')
 166     return (result);
 167
 168   /* Find the amble.  This is the stuff inside this set of braces. */
 169   start = ++i;
 170   c = brace_gobbler (text, tlen, &i, '}');
 171
 172   /* What if there isn't a matching close brace? */
 173   if (c == 0)
 174     {
 175 #if defined (NOTDEF)
 176       /* Well, if we found an unquoted BRACE_ARG_SEPARATOR between START
 177          and I, then this should be an error.  Otherwise, it isn't. */
 178       j = start;
 179       while (j < i)
 180         {
 181           if (text[j] == '\\')
 182             {
 183               j++;
 184               ADVANCE_CHAR (text, tlen, j);
 185               continue;
 186             }
 187
 188           if (text[j] == brace_arg_separator)
 189             {   /* { */
 190               strvec_dispose (result);
 191               last_command_exit_value = 1;
 192               report_error ("no closing `%c' in %s", '}', text);
 193               throw_to_top_level ();
 194             }
 195           ADVANCE_CHAR (text, tlen, j);
 196         }
 197 #endif
 198       free (preamble);          /* Same as result[0]; see initialization. */
 199       result[0] = savestring (text);
 200       return (result);
 201     }
 202
 203 #if defined (SHELL)
 204   amble = substring (text, start, i);
 205   alen = i - start;
 206 #else
 207   amble = (char *)xmalloc (1 + (i - start));
 208   strncpy (amble, &text[start], (i - start));
 209   alen = i - start;
 210   amble[alen] = '\0';
 211 #endif
 212
 213 #if defined (SHELL)
 214   INITIALIZE_MBSTATE;
 215
 216   /* If the amble does not contain an unquoted BRACE_ARG_SEPARATOR, then
 217      just return without doing any expansion.  */
 218   j = 0;
 219   while (amble[j])
 220     {
 221       if (amble[j] == '\\')
 222         {
 223           j++;
 224           ADVANCE_CHAR (amble, alen, j);
 225           continue;
 226         }
 227
 228       if (amble[j] == brace_arg_separator)
 229         break;
 230
 231       ADVANCE_CHAR (amble, alen, j);
 232     }
 233
 234   if (amble[j] == 0)
 235     {
 236       tack = expand_seqterm (amble, alen);
 237       if (tack)
 238         goto add_tack;
 239       else if (text[i + 1])
 240         {
 241           /* If the sequence expansion fails (e.g., because the integers
 242              overflow), but there is more in the string, try and process
 243              the rest of the string, which may contain additional brace
 244              expansions.  Treat the unexpanded sequence term as a simple
 245              string (including the braces). */
 246           tack = strvec_create (2);
 247           tack[0] = savestring (text+start-1);
 248           tack[0][i-start+2] = '\0';
 249           tack[1] = (char *)0;
 250           goto add_tack;
 251         }
 252       else
 253         {
 254           free (amble);
 255           free (preamble);
 256           result[0] = savestring (text);
 257           return (result);
 258         }
 259     }
 260 #endif /* SHELL */
 261
 262   tack = expand_amble (amble, alen, 0);
 263 add_tack:
 264   result = array_concat (result, tack);
 265   free (amble);
 266   if (tack != result)
 267     strvec_dispose (tack);
 268
 269   postamble = text + i + 1;
 270
 271   if (postamble && *postamble)
 272     {
 273       tack = brace_expand (postamble);
 274       result = array_concat (result, tack);
 275       if (tack != result)
 276         strvec_dispose (tack);
 277     }
 278
 279   return (result);
 280 }
 281
 282 /* Expand the text found inside of braces.  We simply try to split the
 283    text at BRACE_ARG_SEPARATORs into separate strings.  We then brace
 284    expand each slot which needs it, until there are no more slots which
 285    need it. */
 286 static char **
 287 expand_amble (text, tlen, flags)
 288      char *text;
 289      size_t tlen;
 290      int flags;
 291 {
 292   char **result, **partial, **tresult;
 293   char *tem;
 294   int start, i, c;
 295
 296 #if defined (SHELL)
 297   DECLARE_MBSTATE;
 298 #endif
 299
 300   result = (char **)NULL;
 301
 302   start = i = 0;
 303   c = 1;
 304   while (c)
 305     {
 306       c = brace_gobbler (text, tlen, &i, brace_arg_separator);
 307 #if defined (SHELL)
 308       tem = substring (text, start, i);
 309 #else
 310       tem = (char *)xmalloc (1 + (i - start));
 311       strncpy (tem, &text[start], (i - start));
 312       tem[i - start] = '\0';
 313 #endif
 314
 315       partial = brace_expand (tem);
 316
 317       if (!result)
 318         result = partial;
 319       else
 320         {
 321           register int lr, lp, j;
 322
 323           lr = strvec_len (result);
 324           lp = strvec_len (partial);
 325
 326           tresult = strvec_mresize (result, lp + lr + 1);
 327           if (tresult == 0)
 328             {
 329               internal_error (_("brace expansion: cannot allocate memory for %s"), tem);
 330               free (tem);
 331               strvec_dispose (partial);
 332               strvec_dispose (result);
 333               result = (char **)NULL;
 334               return result;
 335             }
 336           else
 337             result = tresult;
 338
 339           for (j = 0; j < lp; j++)
 340             result[lr + j] = partial[j];
 341
 342           result[lr + j] = (char *)NULL;
 343           free (partial);
 344         }
 345       free (tem);
 346 #if defined (SHELL)
 347       ADVANCE_CHAR (text, tlen, i);
 348 #else
 349       i++;
 350 #endif
 351       start = i;
 352     }
 353   return (result);
 354 }
 355
 356 #define ST_BAD  0
 357 #define ST_INT  1
 358 #define ST_CHAR 2
 359 #define ST_ZINT 3
 360
 361 #ifndef sh_imaxabs
 362 #  define sh_imaxabs(x) (((x) >= 0) ? (x) : -(x))
 363 #endif
 364
 365 /* Handle signed arithmetic overflow and underflow.  Have to do it this way
 366    to avoid compilers optimizing out simpler overflow checks. */
 367
 368 /* Make sure that a+b does not exceed MAXV or is smaller than MINV (if b < 0).
 369    Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
 370 #define ADDOVERFLOW(a,b,minv,maxv) \
 371         ((((a) > 0) && ((b) > ((maxv) - (a)))) || \
 372          (((a) < 0) && ((b) < ((minv) - (a)))))
 373
 374 /* Make sure that a-b is not smaller than MINV or exceeds MAXV (if b < 0).
 375    Assumes that b > 0 if a > 0 and b < 0 if a < 0 */
 376 #define SUBOVERFLOW(a,b,minv,maxv) \
 377         ((((b) > 0) && ((a) < ((minv) + (b)))) || \
 378          (((b) < 0) && ((a) > ((maxv) + (b)))))
 379
 380 static char **
 381 mkseq (start, end, incr, type, width)
 382      intmax_t start, end, incr;
 383      int type, width;
 384 {
 385   intmax_t n, prevn;
 386   int i, j, nelem;
 387   char **result, *t;
 388
 389   if (incr == 0)
 390     incr = 1;
 391
 392   if (start > end && incr > 0)
 393     incr = -incr;
 394   else if (start < end && incr < 0)
 395     {
 396       if (incr == INTMAX_MIN)           /* Don't use -INTMAX_MIN */
 397         return ((char **)NULL);
 398       incr = -incr;
 399     }
 400
 401   /* Check that end-start will not overflow INTMAX_MIN, INTMAX_MAX.  The +3
 402      and -2, not strictly necessary, are there because of the way the number
 403      of elements and value passed to strvec_create() are calculated below. */
 404   if (SUBOVERFLOW (end, start, INTMAX_MIN+3, INTMAX_MAX-2))
 405     return ((char **)NULL);
 406
 407   prevn = sh_imaxabs (end - start);
 408   /* Need to check this way in case INT_MAX == INTMAX_MAX */
 409   if (INT_MAX == INTMAX_MAX && (ADDOVERFLOW (prevn, 2, INT_MIN, INT_MAX)))
 410     return ((char **)NULL);
 411   /* Make sure the assignment to nelem below doesn't end up <= 0 due to
 412      intmax_t overflow */
 413   else if (ADDOVERFLOW ((prevn/sh_imaxabs(incr)), 1, INTMAX_MIN, INTMAX_MAX))
 414     return ((char **)NULL);
 415
 416   /* XXX - TOFIX: potentially allocating a lot of extra memory if
 417      imaxabs(incr) != 1 */
 418   /* Instead of a simple nelem = prevn + 1, something like:
 419         nelem = (prevn / imaxabs(incr)) + 1;
 420      would work */
 421   nelem = (prevn / sh_imaxabs(incr)) + 1;
 422   if (nelem > INT_MAX - 2)              /* Don't overflow int */
 423     return ((char **)NULL);
 424   result = strvec_mcreate (nelem + 1);
 425   if (result == 0)
 426     {
 427       internal_error (_("brace expansion: failed to allocate memory for %d elements"), nelem);
 428       return ((char **)NULL);
 429     }
 430
 431   /* Make sure we go through the loop at least once, so {3..3} prints `3' */
 432   i = 0;
 433   n = start;
 434   do
 435     {
 436 #if defined (SHELL)
 437       if (ISINTERRUPT)
 438         {
 439           strvec_dispose (result);
 440           result = (char **)NULL;
 441         }
 442       QUIT;
 443 #endif
 444       if (type == ST_INT)
 445         result[i++] = t = itos (n);
 446       else if (type == ST_ZINT)
 447         {
 448           int len, arg;
 449           arg = n;
 450           len = asprintf (&t, "%0*d", width, arg);
 451           result[i++] = t;
 452         }
 453       else
 454         {
 455           if (t = (char *)malloc (2))
 456             {
 457               t[0] = n;
 458               t[1] = '\0';
 459             }
 460           result[i++] = t;
 461         }
 462
 463       /* We failed to allocate memory for this number, so we bail. */
 464       if (t == 0)
 465         {
 466           char *p, lbuf[INT_STRLEN_BOUND(intmax_t) + 1];
 467
 468           /* Easier to do this than mess around with various intmax_t printf
 469              formats (%ld? %lld? %jd?) and PRIdMAX. */
 470           p = inttostr (n, lbuf, sizeof (lbuf));
 471           internal_error (_("brace expansion: failed to allocate memory for `%s'"), p);
 472           strvec_dispose (result);
 473           return ((char **)NULL);
 474         }
 475
 476       /* Handle overflow and underflow of n+incr */
 477       if (ADDOVERFLOW (n, incr, INTMAX_MIN, INTMAX_MAX))
 478         break;
 479
 480       n += incr;
 481
 482       if ((incr < 0 && n < end) || (incr > 0 && n > end))
 483         break;
 484     }
 485   while (1);
 486
 487   result[i] = (char *)0;
 488   return (result);
 489 }
 490
 491 static char **
 492 expand_seqterm (text, tlen)
 493      char *text;
 494      size_t tlen;
 495 {
 496   char *t, *lhs, *rhs;
 497   int i, lhs_t, rhs_t, lhs_l, rhs_l, width;
 498   intmax_t lhs_v, rhs_v, incr;
 499   intmax_t tl, tr;
 500   char **result, *ep, *oep;
 501
 502   t = strstr (text, BRACE_SEQ_SPECIFIER);
 503   if (t == 0)
 504     return ((char **)NULL);
 505
 506   lhs_l = t - text;             /* index of start of BRACE_SEQ_SPECIFIER */
 507   lhs = substring (text, 0, lhs_l);
 508   rhs = substring (text, lhs_l + sizeof(BRACE_SEQ_SPECIFIER) - 1, tlen);
 509
 510   if (lhs[0] == 0 || rhs[0] == 0)
 511     {
 512       free (lhs);
 513       free (rhs);
 514       return ((char **)NULL);
 515     }
 516
 517   /* Now figure out whether LHS and RHS are integers or letters.  Both
 518      sides have to match. */
 519   lhs_t = (legal_number (lhs, &tl)) ? ST_INT :
 520                 ((ISALPHA (lhs[0]) && lhs[1] == 0) ?  ST_CHAR : ST_BAD);
 521
 522   /* Decide on rhs and whether or not it looks like the user specified
 523      an increment */
 524   ep = 0;
 525   if (ISDIGIT (rhs[0]) || ((rhs[0] == '+' || rhs[0] == '-') && ISDIGIT (rhs[1])))
 526     {
 527       rhs_t = ST_INT;
 528       errno = 0;
 529       tr = strtoimax (rhs, &ep, 10);
 530       if (errno == ERANGE || (ep && *ep != 0 && *ep != '.'))
 531         rhs_t = ST_BAD;                 /* invalid */
 532     }
 533   else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.'))
 534     {
 535       rhs_t = ST_CHAR;
 536       ep = rhs + 1;
 537     }
 538   else
 539     {
 540       rhs_t = ST_BAD;
 541       ep = 0;
 542     }
 543
 544   incr = 1;
 545   if (rhs_t != ST_BAD)
 546     {
 547       oep = ep;
 548       errno = 0;
 549       if (ep && *ep == '.' && ep[1] == '.' && ep[2])
 550         incr = strtoimax (ep + 2, &ep, 10);
 551       if (*ep != 0 || errno == ERANGE)
 552         rhs_t = ST_BAD;                 /* invalid incr or overflow */
 553       tlen -= ep - oep;
 554     }
 555
 556   if (lhs_t != rhs_t || lhs_t == ST_BAD || rhs_t == ST_BAD)
 557     {
 558       free (lhs);
 559       free (rhs);
 560       return ((char **)NULL);
 561     }
 562
 563   /* OK, we have something.  It's either a sequence of integers, ascending
 564      or descending, or a sequence or letters, ditto.  Generate the sequence,
 565      put it into a string vector, and return it. */
 566
 567   if (lhs_t == ST_CHAR)
 568     {
 569       lhs_v = (unsigned char)lhs[0];
 570       rhs_v = (unsigned char)rhs[0];
 571       width = 1;
 572     }
 573   else
 574     {
 575       lhs_v = tl;               /* integer truncation */
 576       rhs_v = tr;
 577
 578       /* Decide whether or not the terms need zero-padding */
 579       rhs_l = tlen - lhs_l - sizeof (BRACE_SEQ_SPECIFIER) + 1;
 580       width = 0;
 581       if (lhs_l > 1 && lhs[0] == '0')
 582         width = lhs_l, lhs_t = ST_ZINT;
 583       if (lhs_l > 2 && lhs[0] == '-' && lhs[1] == '0')
 584         width = lhs_l, lhs_t = ST_ZINT;
 585       if (rhs_l > 1 && rhs[0] == '0' && width < rhs_l)
 586         width = rhs_l, lhs_t = ST_ZINT;
 587       if (rhs_l > 2 && rhs[0] == '-' && rhs[1] == '0' && width < rhs_l)
 588         width = rhs_l, lhs_t = ST_ZINT;
 589
 590       if (width < lhs_l && lhs_t == ST_ZINT)
 591         width = lhs_l;
 592       if (width < rhs_l && lhs_t == ST_ZINT)
 593         width = rhs_l;
 594     }
 595
 596   result = mkseq (lhs_v, rhs_v, incr, lhs_t, width);
 597
 598   free (lhs);
 599   free (rhs);
 600
 601   return (result);
 602 }
 603
 604 /* Start at INDEX, and skip characters in TEXT. Set INDEX to the
 605    index of the character matching SATISFY.  This understands about
 606    quoting.  Return the character that caused us to stop searching;
 607    this is either the same as SATISFY, or 0. */
 608 /* If SATISFY is `}', we are looking for a brace expression, so we
 609    should enforce the rules that govern valid brace expansions:
 610         1) to count as an arg separator, a comma or `..' has to be outside
 611            an inner set of braces.
 612 */
 613 static int
 614 brace_gobbler (text, tlen, indx, satisfy)
 615      char *text;
 616      size_t tlen;
 617      int *indx;
 618      int satisfy;
 619 {
 620   register int i, c, quoted, level, commas, pass_next;
 621 #if defined (SHELL)
 622   int si;
 623   char *t;
 624 #endif
 625   DECLARE_MBSTATE;
 626
 627   level = quoted = pass_next = 0;
 628 #if defined (CSH_BRACE_COMPAT)
 629   commas = 1;
 630 #else
 631   commas = (satisfy == '}') ? 0 : 1;
 632 #endif
 633
 634   i = *indx;
 635   while (c = text[i])
 636     {
 637       if (pass_next)
 638         {
 639           pass_next = 0;
 640 #if defined (SHELL)
 641           ADVANCE_CHAR (text, tlen, i);
 642 #else
 643           i++;
 644 #endif
 645           continue;
 646         }
 647
 648       /* A backslash escapes the next character.  This allows backslash to
 649          escape the quote character in a double-quoted string. */
 650       if (c == '\\' && (quoted == 0 || quoted == '"' || quoted == '`'))
 651         {
 652           pass_next = 1;
 653           i++;
 654           continue;
 655         }
 656
 657 #if defined (SHELL)
 658       /* If compiling for the shell, treat ${...} like \{...} */
 659       if (c == '$' && text[i+1] == '{' && quoted != '\'')               /* } */
 660         {
 661           pass_next = 1;
 662           i++;
 663           if (quoted == 0)
 664             level++;
 665           continue;
 666         }
 667 #endif
 668
 669       if (quoted)
 670         {
 671           if (c == quoted)
 672             quoted = 0;
 673 #if defined (SHELL)
 674           /* The shell allows quoted command substitutions */
 675           if (quoted == '"' && c == '$' && text[i+1] == '(')    /*)*/
 676             goto comsub;
 677 #endif
 678 #if defined (SHELL)
 679           ADVANCE_CHAR (text, tlen, i);
 680 #else
 681           i++;
 682 #endif
 683           continue;
 684         }
 685
 686       if (c == '"' || c == '\'' || c == '`')
 687         {
 688           quoted = c;
 689           i++;
 690           continue;
 691         }
 692
 693 #if defined (SHELL)
 694       /* Pass new-style command and process substitutions through unchanged. */
 695       if ((c == '$' || c == '<' || c == '>') && text[i+1] == '(')                       /* ) */
 696         {
 697 comsub:
 698           si = i + 2;
 699           t = extract_command_subst (text, &si, 0);
 700           i = si;
 701           free (t);
 702           i++;
 703           continue;
 704         }
 705 #endif
 706
 707       if (c == satisfy && level == 0 && quoted == 0 && commas > 0)
 708         {
 709           /* We ignore an open brace surrounded by whitespace, and also
 710              an open brace followed immediately by a close brace preceded
 711              by whitespace.  */
 712           if (c == '{' &&
 713               ((!i || brace_whitespace (text[i - 1])) &&
 714                (brace_whitespace (text[i + 1]) || text[i + 1] == '}')))
 715             {
 716               i++;
 717               continue;
 718             }
 719
 720             break;
 721         }
 722
 723       if (c == '{')
 724         level++;
 725       else if (c == '}' && level)
 726         level--;
 727 #if !defined (CSH_BRACE_COMPAT)
 728       else if (satisfy == '}' && c == brace_arg_separator && level == 0)
 729         commas++;
 730       else if (satisfy == '}' && STREQN (text+i, BRACE_SEQ_SPECIFIER, 2) &&
 731                 text[i+2] != satisfy && level == 0)
 732         commas++;
 733 #endif
 734
 735 #if defined (SHELL)
 736       ADVANCE_CHAR (text, tlen, i);
 737 #else
 738       i++;
 739 #endif
 740     }
 741
 742   *indx = i;
 743   return (c);
 744 }
 745
 746 /* Return 1 if ARR has any non-empty-string members.  Used to short-circuit
 747    in array_concat() below. */
 748 static int
 749 degenerate_array (arr)
 750      char **arr;
 751 {
 752   register int i;
 753
 754   for (i = 0; arr[i]; i++)
 755     if (arr[i][0] != '\0')
 756       return 0;
 757   return 1;
 758 }
 759
 760 /* Return a new array of strings which is the result of appending each
 761    string in ARR2 to each string in ARR1.  The resultant array is
 762    len (arr1) * len (arr2) long.  For convenience, ARR1 (and its contents)
 763    are free ()'ed.  ARR1 can be NULL, in that case, a new version of ARR2
 764    is returned. */
 765 static char **
 766 array_concat (arr1, arr2)
 767      char **arr1, **arr2;
 768 {
 769   register int i, j, len, len1, len2;
 770   register char **result;
 771
 772   if (arr1 == 0)
 773     return (arr2);              /* XXX - see if we can get away without copying? */
 774
 775   if (arr2 == 0)
 776     return (arr1);              /* XXX - caller expects us to free arr1 */
 777
 778   /* We can only short-circuit if the array consists of a single null element;
 779      otherwise we need to replicate the contents of the other array and
 780      prefix (or append, below) an empty element to each one. */
 781   if (arr1[0] && arr1[0][0] == 0 && arr1[1] == 0)
 782     {
 783       strvec_dispose (arr1);
 784       return (arr2);            /* XXX - use flags to see if we can avoid copying here */
 785     }
 786
 787   if (arr2[0] && arr2[0][0] == 0 && arr2[1] == 0)
 788     return (arr1);              /* XXX - rather than copying and freeing it */
 789
 790   len1 = strvec_len (arr1);
 791   len2 = strvec_len (arr2);
 792
 793   result = (char **)xmalloc ((1 + (len1 * len2)) * sizeof (char *));
 794
 795   len = 0;
 796   for (i = 0; i < len1; i++)
 797     {
 798       int strlen_1 = strlen (arr1[i]);
 799
 800       for (j = 0; j < len2; j++)
 801         {
 802           result[len] = (char *)xmalloc (1 + strlen_1 + strlen (arr2[j]));
 803           strcpy (result[len], arr1[i]);
 804           strcpy (result[len] + strlen_1, arr2[j]);
 805           len++;
 806         }
 807       free (arr1[i]);
 808     }
 809   free (arr1);
 810
 811   result[len] = (char *)NULL;
 812   return (result);
 813 }
 814
 815 #if defined (TEST)
 816 #include <stdio.h>
 817
 818 void *
 819 xmalloc(n)
 820      size_t n;
 821 {
 822   return (malloc (n));
 823 }
 824
 825 void *
 826 xrealloc(p, n)
 827      void *p;
 828      size_t n;
 829 {
 830   return (realloc (p, n));
 831 }
 832
 833 int
 834 internal_error (format, arg1, arg2)
 835      char *format, *arg1, *arg2;
 836 {
 837   fprintf (stderr, format, arg1, arg2);
 838   fprintf (stderr, "\n");
 839 }
 840
 841 main ()
 842 {
 843   char example[256];
 844
 845   for (;;)
 846     {
 847       char **result;
 848       int i;
 849
 850       fprintf (stderr, "brace_expand> ");
 851
 852       if ((!fgets (example, 256, stdin)) ||
 853           (strncmp (example, "quit", 4) == 0))
 854         break;
 855
 856       if (strlen (example))
 857         example[strlen (example) - 1] = '\0';
 858
 859       result = brace_expand (example);
 860
 861       for (i = 0; result[i]; i++)
 862         printf ("%s\n", result[i]);
 863
 864       strvec_dispose (result);
 865     }
 866 }
 867 \f
 868 /*
 869  * Local variables:
 870  * compile-command: "gcc -g -Bstatic -DTEST -o brace_expand braces.c general.o"
 871  * end:
 872  */
 873
 874 #endif /* TEST */
 875 #endif /* BRACE_EXPANSION */