braces.c

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