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