Brace expansion

Brace expansion is a type of parameter expansion made popular by Unix shells, where it allows users to specify multiple similar string parameters without having to type them all out. E.g. the parameter enable_{audio,video} would be interpreted as if both enable_audio and enable_video had been specified.

Brace expansion is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Task

Write a function that can perform brace expansion on any input string.
Briefly show how it would be used.

Specification

For the purposes of this task, "brace expansion" shall be defined according to the following specification. Please try to comply with it exactly, even when inconvenient, to ensure that all implementations are comparable. (See #Perl for a reference implementation.)

• These characters (and only these!) are to be interpreted as potential meta-characters in the input string:

  {	opens an alternation group
  ,	separates alternatives inside an alternation group
  }	closes the last opened alternation group
  \	escapes the immediately following character, to prevent it from being treated as a meta-character

• A valid alternation group consists of a balanced pair of braces containing two or more comma-separated alternatives (e.g. {,} or {foo,bar} or {,foo,bar} or {foo,bar,,baz}). The brace and comma characters that make up such a group are not passed along to the output; instead, the number of outputs is multiplied by the number of alternatives, each copy featuring one of the alternatives in the place in the string where the alternation group used to be.
• The multiplication of outputs caused by two or more alternation groups in the same string is cumulative (e.g. {a,b}{1,2} --> a1  a2  b1  b2)
• The rules for parsing/expanding the whole string also apply recursively to each alternative of an alternation group, so nested groups result in nested expansion (e.g. {aa,bb{cc,dd}} --> aa  bbcc  bbdd)
• Extraneous brace and comma characters which are not part of a valid alternation group, should be passed along to the output unchanged. These are:
  • commas which are not contained by any balanced brace pair
  • brace pairs which don't contain at least two alternatives (e.g. {} or {foo})
  • opening braces which don't have a matching closing brace (or vice versa)
• All backslashes should be passed along to the output unchanged (despite being interpreted as meta-characters).
• The code should be able to handle inputs with arbitrary numbers of brace groups and nesting levels (limited only by the computer's memory or by a reasonably high recursion limit).
• Results should be returned in the form of an array/list-like data structure (suitable for further processing within the same program), and in the order demonstrated below (i.e. as if the original brace groups were used as sort keys for lexicographic ordering).

Test Cases

Input	Ouput
~/{Downloads,Pictures}/*.{jpg,gif,png}	~/Downloads/*.jpg ~/Downloads/*.gif ~/Downloads/*.png ~/Pictures/*.jpg ~/Pictures/*.gif ~/Pictures/*.png
It{{em,alic}iz,erat}e{d,}, please.	Itemized, please. Itemize, please. Italicized, please. Italicize, please. Iterated, please. Iterate, please.
{,{,gotta have{,\, again\, }}more }cowbell!	cowbell! more cowbell! gotta have more cowbell! gotta have, again, more cowbell!
{}} some {\\{edge,edgy} }{ cases, here\\\}	{}} some {\\edge }{ cases, here\\\} {}} some {\\edgy }{ cases, here\\\}

Motivation

The point of this task is to show how different programming languages deal with a real-life problem that combines:

• simple lexing (to deal with backslash escapes)
• fault-tolerant parsing (i.e. handling all inputs, even partially invalid ones, without aborting)
• list transformation (Conceptually, this task involves parsing linear information into a tree, and then recursively flattening it while applying the Cartesian product to each level. But feel free to take shortcuts!)

So if your language provides ready-to-use brace expansion functionality, then by all means mention it, but please also show a solution that implements it manually.