This is super cool! I've played with it a bit and except for a few minor issues (mostly with ranges) it works like a charm! (I've just committed an enhanced version of the test that reveals these problems.) About the interface: http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/include/rw_braceexp.h?r=628611 Can the third argument be negative? (If not, it might make sense to change its type to size_t). What about the sep argument? Can it be outside of the range of char, such as -1? It seems to just get converted to char here (oooh, line number links ;-): http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/src/braceexp.cpp?r=628817#l274 It might make sense to do some basic checking on it (and on the other arguments) in rw_brace_expand() before passing it to the implementation. A few questions/comments on the implementation: http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/src/braceexp.cpp?r=628817 The _rw_is_lower() and _rw_is_upper() helper functions should either be replaced with the C equivalents or rewritten to handle EBCDIC. If the latter, I suggest making them inline. In _rw_brace_graph, the member functions don't need to be privatized (with the _C_ prefix). Also, unless the class is intended to be copy constructible and assignable I suggest to explicitly declare the two members private. Finally, please check your braces :) E.g., these: http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/src/braceexp.cpp?r=628817#l29 http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/src/braceexp.cpp?r=628817#l54 http://fisheye6.cenqua.com/browse/stdcxx/trunk/tests/src/braceexp.cpp?r=628817#l87 Martin vitek@apache.org wrote: > Author: vitek > Date: Sun Feb 17 20:35:15 2008 > New Revision: 628611 > > URL: http://svn.apache.org/viewvc?rev=628611&view=rev > Log: > > 2008-02-17 Travis Vitek > > STDCXX-714 > * tests/include/rw_braceexp.h: Added a new header to declare the test > suite helper function rw_brace_expand(). > * tests/src/braceexp.cpp: New source file to define rw_brace_expand(). > * tests/self/0.braceexp.cpp: New test to exercise rw_brace_expand() > > > Added: > stdcxx/trunk/tests/include/rw_braceexp.h > stdcxx/trunk/tests/self/0.braceexp.cpp > stdcxx/trunk/tests/src/braceexp.cpp > > Added: stdcxx/trunk/tests/include/rw_braceexp.h > URL: http://svn.apache.org/viewvc/stdcxx/trunk/tests/include/rw_braceexp.h?rev=628611&view=auto > ============================================================================== > --- stdcxx/trunk/tests/include/rw_braceexp.h (added) > +++ stdcxx/trunk/tests/include/rw_braceexp.h Sun Feb 17 20:35:15 2008 > @@ -0,0 +1,43 @@ > +/************************************************************************ > + * > + * rw_braceexp.h - declarations of testsuite helpers > + * > + * $Id$ > + * > + ************************************************************************ > + * > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed > + * with this work for additional information regarding copyright > + * ownership. The ASF licenses this file to you under the Apache > + * License, Version 2.0 (the "License"); you may not use this file > + * except in compliance with the License. You may obtain a copy of > + * the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or > + * implied. See the License for the specific language governing > + * permissions and limitations under the License. > + * > + **************************************************************************/ > + > +#ifndef RW_BRACEEXP_H_INCLUDED > +#define RW_BRACEEXP_H_INCLUDED > + > + > +#include > + > + > +// rw_brace_expand() performs brace expansion according to chapter 3.5.1 of > +// the Bash Reference Manual with the exception of special handling for the > +// string `${'. > + > +_TEST_EXPORT char* > +rw_brace_expand (const char* brace_expr, char* s, int n, int sep); > + > + > +#endif // RW_BRACEEXP_H_INCLUDED > + > > Added: stdcxx/trunk/tests/self/0.braceexp.cpp > URL: http://svn.apache.org/viewvc/stdcxx/trunk/tests/self/0.braceexp.cpp?rev=628611&view=auto > ============================================================================== > --- stdcxx/trunk/tests/self/0.braceexp.cpp (added) > +++ stdcxx/trunk/tests/self/0.braceexp.cpp Sun Feb 17 20:35:15 2008 > @@ -0,0 +1,121 @@ > +/************************************************************************ > + * > + * 0.braceexp.cpp - tests exercising the rw_brace_expand() helper > + * > + * $Id$ > + * > + ************************************************************************ > + * > + * Licensed to the Apache Software Foundation (ASF) under one or more > + * contributor license agreements. See the NOTICE file distributed > + * with this work for additional information regarding copyright > + * ownership. The ASF licenses this file to you under the Apache > + * License, Version 2.0 (the "License"); you may not use this file > + * except in compliance with the License. You may obtain a copy of > + * the License at > + * > + * http://www.apache.org/licenses/LICENSE-2.0 > + * > + * Unless required by applicable law or agreed to in writing, software > + * distributed under the License is distributed on an "AS IS" BASIS, > + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or > + * implied. See the License for the specific language governing > + * permissions and limitations under the License. > + * > + **************************************************************************/ > + > +#include > + > +#include // for fprintf(), stderr > +#include // for free() > +#include // for strcmp() > + > +// the number of failed tests > +static int nerrors; > + > +static void > +test (int line, const char* brace_expr, const char* expect) > +{ > + char buf [128]; > + > + char* result = rw_brace_expand (brace_expr, buf, sizeof (buf), ' '); > + > + const bool equal = (expect && result) > + ? !strcmp (expect, result) > + : expect == result; > + > + if (!equal) { > + > + ++nerrors; > + > + fprintf (stderr, > + "%d. rw_brace_expand(\"%s\", ...) failed. " > + "expected \"%s\" got \"%s\"\n", > + line, brace_expr, > + expect ? expect : "(null)", > + result ? result : "(null)"); > + } > + > + if (result != buf) > + free (result); > +} > + > +int main () > +{ > +#define TEST(s,e) test (__LINE__, s, e) > + > + TEST ("a", "a"); > + TEST ("a\\b", "ab"); > + > + TEST ("{0}" , "{0}"); > + TEST ("\\{0}", "{0}"); > + TEST ("{\\0}", "{0}"); > + TEST ("{0\\}", "{0}"); > + > + TEST ("{0..1}", "0 1"); > + TEST ("\\{0..1}", "{0..1}"); > + TEST ("{\\0..1}", "{0..1}"); > + TEST ("{0\\..1}", "{0..1}"); > + TEST ("{0..\\1}", "{0..1}"); > + TEST ("{0..1\\}", "{0..1}"); > + > + TEST ("a{0}", "a{0}"); > + TEST ("a{0}b", "a{0}b"); > + TEST ("a\\{0\\}b", "a{0}b"); > + TEST ("a\\{0,123,4\\}b", "a{0,123,4}b"); > + > + TEST ("{0..a}", "{0..a}"); > + TEST ("{a..0}", "{a..0}"); > + > + TEST ("{0..0}", "0"); > + TEST ("{0..5}", "0 1 2 3 4 5"); > + TEST ("{4..2}", "4 3 2"); > + TEST ("{a..g}", "a b c d e f g"); > + TEST ("{g..c}", "g f e d c"); > + TEST ("{A..G}", "A B C D E F G"); > + TEST ("{G..C}", "G F E D C"); > + > + TEST ("{,}", ""); > + TEST ("{abc,def}", "abc def"); > + TEST ("{ab\\c,d\\ef}", "abc def"); > + TEST ("abc{d,e,f}", "abcd abce abcf"); > + > + TEST ("z{c,a{d..f}a,c}z", "zcz zadaz zaeaz zafaz zcz"); > + TEST ("z{c,a{d,e,f}a,c}z", "zcz zadaz zaeaz zafaz zcz"); > + > + TEST ("{abc,{,d,e,f,}}", "abc d e f"); > + TEST ("{abc,{,d,e,f,}}{x,y}", "abcx abcy x y dx dy ex ey fx fy x y"); > + TEST ("{abc,{,d\\,e\\,f,}}", "abc d,e,f"); > + > + TEST ("A{0..3}", "A0 A1 A2 A3"); > + TEST ("A{0..2}{6..7}", "A06 A07 A16 A17 A26 A27"); > + TEST ("A{A}{0..3}", "A{A}{0..3}"); > + TEST ("A{0..3}{A}", "A0{A} A1{A} A2{A} A3{A}"); > + > + TEST ("A{0,{4..7}{,}}", "A0 A4 A4 A5 A5 A6 A6 A7 A7"); > + TEST ("a{1,3,x{5..9}y}b", "a1b a3b ax5yb ax6yb ax7yb ax8yb ax9yb"); > + TEST ("{en,es}_{US,MX}.*", "en_US.* en_MX.* es_US.* es_MX.*"); > + > + // return 0 on success, 1 on failure > + return !(0 == nerrors); > +} > > Added: stdcxx/trunk/tests/src/braceexp.cpp > URL: http://svn.apache.org/viewvc/stdcxx/trunk/tests/src/braceexp.cpp?rev=628611&view=auto > ============================================================================== > --- stdcxx/trunk/tests/src/braceexp.cpp (added) > +++ stdcxx/trunk/tests/src/braceexp.cpp Sun Feb 17 20:35:15 2008 > @@ -0,0 +1,717 @@ > +#include > +#include > + > + > +static int _rw_is_digit (int ch) > +{ > + return !(ch < '0' || '9' < ch); > +} > + > +static int _rw_is_lower (int ch) > +{ > + return !(ch < 'a' || 'z' < ch); > +} > + > +static int _rw_is_upper (int ch) > +{ > + return !(ch < 'A' || 'Z' < ch); > +} > + > +// search `beg' to `end' for the next unescaped open brace . if `end' > +// is 0 then the search will terminate at the end of string. returns 0 > +// on failure. > +static const char* _rw_find_open_brace (const char* beg, > + const char* end) > +{ > + bool is_escaped = false; > + > + for (/**/; *beg; ++beg) > + { > + if (end && !(beg < end)) > + break; > + > + const bool is_match = (*beg == '{'); > + if (!is_escaped && is_match) { > + return beg; > + } > + > + is_escaped = !is_escaped && (*beg == '\\'); > + } > + > + return 0; > +} > + > +// search `beg' to `end' for the next close brace at the current brace > +// depth. if `end' is 0, the search will continue until a match or end > +// of string. returns 0 on failure. > +static const char* _rw_find_close_brace (const char* beg, > + const char* end) > +{ > + bool is_escaped = false; > + > + // nested brace depth > + for (int depth = 1; *beg; ++beg) > + { > + if (end && !(beg < end)) > + break; > + > + const bool is_open_brace = (*beg == '{'); > + if (!is_escaped && is_open_brace) { > + ++depth; > + } > + > + const bool is_close_brace = (*beg == '}'); > + if (!is_escaped && is_close_brace) { > + --depth; > + } > + > + is_escaped = !is_escaped && (*beg == '\\'); > + > + if (depth == 0) > + return beg; > + } > + > + return 0; > +} > + > +// search `beg' to `end' for the next unescaped comma at the current > +// brace depth. if `end' is 0, the search will continue until a match > +// or end of string. returns 0 on failure. > +static const char* _rw_find_next_comma (const char* beg, > + const char* end) > +{ > + bool is_escaped = false; > + > + // nested brace depth > + for (int depth = 0; *beg; ++beg) > + { > + if (end && !(beg < end)) > + break; > + > + const bool is_open_brace = (*beg == '{'); > + if (!is_escaped && is_open_brace) { > + ++depth; > + } > + > + const bool is_close_brace = (*beg == '}'); > + if (!is_escaped && is_close_brace) { > + --depth; > + } > + > + const bool is_comma = (*beg == ','); > + if (!is_escaped && is_comma) { > + if (depth == 0) > + return beg; > + } > + > + is_escaped = !is_escaped && (*beg == '\\'); > + } > + > + return 0; > +} > + > + > + > +// this is where most of the work is done. > +struct _rw_brace_graph > +{ > + // > + _rw_brace_graph (); > + > + // > + ~_rw_brace_graph (); > + > + // expand `brace_expr' into `len' bytes of `buf'. if it won't fit, we > + // allocate a buffer with malloc() and return that. so the user needs > + // to free() the return buffer if it is not equal to `buf'. > + char* _C_build_and_expand (const char* brace_expr, > + char* buf, int len, int sep); > + > +private: > + > + // node for a directed-acyclic-graph that we build from the original > + // brace expression > + struct _rw_brace_node > + { > + const char* str_; > + int len_; > + > + _rw_brace_node* sibling_; > + _rw_brace_node* child_; > + }; > + > + // retrieve a new node. nodes are allocated in large blocks. those > + // blocks are deallocated when this graph instance is destroyed. > + _rw_brace_node* _C_get_new_node (); > + > + // this function generates a dag from an arbitrary brace expression. > + // the format is `prefix{body}suffix'. prefix, and suffix can both > + // be the empty string. body may be a comma seperated list of tokens, > + // a range of tokens, or arbitrary literal text. escapes on commas > + // and braces are ignored, and left intact otherwise. > + _rw_brace_node* _C_build_anything (const char* beg, const char* end); > + > + // generates a dag from an arbitrary range brace expression. the > + // format is `{?..?}suffix' where both ? are alphanumeric digits > + // of the same character class. > + _rw_brace_node* _C_build_range (const char* beg, const char* end); > + > + // generates a dag from an arbitrary list brace expression. the > + // format is `{a,b[,c]}suffix', where `a', `b' and `c' are full > + // brace expansions that would be processed by _C_build_anything. > + _rw_brace_node* _C_build_list (const char* beg, const char* end); > + > + // generates a dag from literal text. no brace expansion is done > + // on the literal text. > + _rw_brace_node* _C_build_literal (const char* beg, const char* end); > + > + // the number of nodes held by each brace buffer [see below] > + enum { _C_size = 64 }; > + > + // buffer to avoid many small allocations > + struct _rw_brace_buffer > + { > + _rw_brace_node nodes_ [_C_size]; > + _rw_brace_buffer* next_; > + }; > + > + // the initial set of nodes is preallocated as part of this graph > + // object instance. additional blocks of nodes will be allocated > + // as is necessary by the _C_get_new_node() member. > + _rw_brace_buffer node_cache_; > + > + int used_; // number of nodes used in the last buffer > + _rw_brace_buffer* nodes_; // pointer to last allocated node buffer > + > + // code for generating the string > + > + bool _C_append (const char* beg, int n); > + > + char* user_buf_; // this is the buffer > + char* string_buf_; > + int string_cap_; > + int string_len_; > + > + // we use this to walk the stack. we need to walk from the root > + // of the tree to each leaf. when we reach a leaf, we need a way > + // to see the path that we took to get where we are. we use this > + // path to write out each part of the full expansion. > + struct _rw_recursion_context > + { > + _rw_recursion_context (_rw_brace_node* node) > + : parent_ (0), node_ (node) > + { > + } > + > + _rw_recursion_context (_rw_recursion_context* parent) > + : parent_ (parent), node_ (parent->node_->child_) > + { > + } > + > + _rw_recursion_context* parent_; > + _rw_brace_node* node_; > + }; > + > + // this function walks the dag, leaving a trail of context > + // objects so we can walk back to the root and write the data > + // at each level in the graph. > + bool _C_brace_expand (_rw_recursion_context* self, char sep); > + > + // this function writes the data at each level of the dag > + // to our internal buffer. > + bool _C_brace_expand_write (_rw_recursion_context* context); > +}; > + > +_rw_brace_graph::_rw_brace_graph () > + : used_ (0) > + , nodes_ (&node_cache_) > + , user_buf_ (0) > + , string_buf_ (0) > + , string_cap_ (0) > + , string_len_ (0) > +{ > + node_cache_.next_ = 0; > +} > + > +_rw_brace_graph::~_rw_brace_graph () > +{ > + _rw_brace_buffer* nodes = node_cache_.next_; > + while (nodes) > + { > + _rw_brace_buffer* next = nodes->next_; > + nodes->next_ = 0; > + > + // deallocate this buffer > + free (nodes); > + > + // setup to deallocate next one > + nodes = next; > + } > +} > + > + > + > +char* > +_rw_brace_graph::_C_build_and_expand (const char* brace_expr, > + char* buf, int len, int sep) > +{ > + const int brace_expr_len = strlen (brace_expr); > + > + _rw_brace_node* root = _C_build_anything (brace_expr, > + brace_expr + brace_expr_len); > + if (!root) > + return 0; > + > + // setup for the expansion > + user_buf_ = buf; > + string_buf_ = buf; > + string_cap_ = len; > + string_len_ = 0; > + > + // this helps us do the building of the output string > + _rw_recursion_context context (root); > + > + if (!_C_brace_expand (&context, sep)) > + { > + if (string_buf_ != user_buf_) > + free (string_buf_); > + string_buf_ = 0; > + } > + > + // kill the last seperator with a null terminator > + else if (string_buf_) > + { > + const int pos = string_len_ < 1 ? 0 : string_len_ - 1; > + string_buf_ [pos] = '\0'; > + } > + > + return string_buf_; > +} > + > +_rw_brace_graph::_rw_brace_node* > +_rw_brace_graph::_C_get_new_node () > +{ > + used_ += 1; > + > + // if we run out of space, grab a new block > + if (! (used_ < _C_size)) > + { > + nodes_->next_ > + = (_rw_brace_buffer*)malloc (sizeof (_rw_brace_buffer)); > + if (!nodes_->next_) > + return 0; > + > + nodes_ = nodes_->next_; > + nodes_->next_ = 0; > + > + used_ -= _C_size; > + } > + > + _rw_brace_node* node = &nodes_->nodes_ [used_ - 1]; > + node->str_ = 0; > + node->len_ = 0; > + node->sibling_ = 0; > + node->child_ = 0; > + > + return node; > +} > + > +_rw_brace_graph::_rw_brace_node* > +_rw_brace_graph::_C_build_anything (const char* beg, const char* end) > +{ > + // > + const char* open_brace = _rw_find_open_brace (beg, end); > + if (open_brace) > + { > + // build a node for the prefix if there is one > + _rw_brace_node* prefix = _C_get_new_node (); > + prefix->str_ = beg; > + prefix->len_ = (open_brace - beg); > + > + // try to build a range expansion > + _rw_brace_node* child = 0; > + > + child = _C_build_range (open_brace, end); > + if (!child) { > + > + // try to do a list expansion > + child = _C_build_list (open_brace, end); > + if (!child) { > + > + // try to do a literal expansion > + child = _C_build_literal (open_brace, end); > + if (!child) { > + return 0; > + } > + } > + } > + > + // we must have a valid child pointer at this point > + prefix->child_ = child; > + > + return prefix; > + } > + > + // there was no open brace, so the entire text from beg to end > + // is a literal > + _rw_brace_node* prefix = _C_get_new_node (); > + if (!prefix) > + return 0; > + > + prefix->str_ = beg; > + prefix->len_ = (end - beg); > + > + return prefix; > +} > + > +_rw_brace_graph::_rw_brace_node* > +_rw_brace_graph::_C_build_literal (const char* beg, const char* end) > +{ > + _rw_brace_node* prefix = _C_get_new_node (); > + if (!prefix) > + return 0; > + > + prefix->str_ = beg; > + prefix->len_ = (end - beg); > + > + return prefix; > +} > + > +_rw_brace_graph::_rw_brace_node* > +_rw_brace_graph::_C_build_range (const char* beg, const char* end) > +{ > + // check for {a..z} type range expression. make sure not to > + // reference past the end of the string. > + if ( beg [0] != '{' > + || beg [1] == '\0' > + || beg [2] != '.' > + || beg [3] != '.' > + || beg [4] == '\0' > + || beg [5] != '}') > + return 0; > + > + // grab characters that represent the start and end of the range > + char cbeg = beg [1]; > + char cend = beg [4]; > + > + // only works if range characters are both digit, lower or upper. > + const int both_are_digit = _rw_is_digit (cbeg) && _rw_is_digit (cend); > + const int both_are_lower = _rw_is_lower (cbeg) && _rw_is_lower (cend); > + const int both_are_upper = _rw_is_upper (cbeg) && _rw_is_upper (cend); > + > + if (! (both_are_digit || both_are_lower || both_are_upper)) > + return false; > + > + // these must live for duration of program > + static const char* table [] = > + { > + "0123456789", // 0 > + "abcdefghijklmnopqrstuvwxyz", // 1 > + "ABCDEFGHIJKLMNOPQRSTUVWXYZ", // 2 > + }; > + > + const int idx = (both_are_lower << 0) + > + (both_are_upper << 1); > + > + const int dir = (cbeg < cend) ? 1 : -1; > + > + // build the suffix > + _rw_brace_node* suffix = _C_build_anything (beg + 6, end); > + if (!suffix) > + return false; // failed to parse suffix > + > + _rw_brace_node* first_child = 0; > + _rw_brace_node* final_child = 0; > + > + // build a list of children, associate each with suffix > + for (/**/; cbeg != cend; cbeg += dir) { > + > + // create a child from whatever is between beg and end. that childs > + // next pointer will be the suffix we created above. > + _rw_brace_node* child = _C_get_new_node (); > + if (!child) { > + return false; > + } > + > + // this finds beg in our array, we could have used strchr > + child->str_ = table [idx] + (cbeg - table [idx][0]); > + child->len_ = 1; > + > + // track children we have created > + if (!first_child) > + first_child = child; > + > + if (final_child) > + final_child->sibling_ = child; > + final_child = child; > + > + // suffix is the suffix of the child expression > + while (child->child_) > + child = child->child_; > + child->child_ = suffix; > + } > + > + // create the last node in the range. > + _rw_brace_node* child = _C_get_new_node (); > + if (!child) { > + return false; > + } > + > + child->str_ = table [idx] + (cbeg - table [idx][0]); > + child->len_ = 1; > + > + // trach child > + if (!first_child) > + first_child = child; > + > + if (final_child) > + final_child->sibling_ = child; > + final_child = child; > + > + // suffix is the suffix of the child expression > + while (child->child_) > + child = child->child_; > + child->child_ = suffix; > + > + return first_child; > +} > + > +_rw_brace_graph::_rw_brace_node* > +_rw_brace_graph::_C_build_list (const char* beg, const char* end) > +{ > + // > + // {abc,d{1..3}e}f > + // ^ ^ > + // > + // prefix '' > + // suffix 'f' > + // middle '{abc,d{1..3}e}' > + > + // generate node for prefix [which is a literal, and is handled by the caller > + // generate node for the suffix [which is anything] > + > + // generate list of nodes for the middle [each of which are anything] > + // set the next pointer of each to the suffix, and set next pointer > + // of the prefix to the first list item. > + > + // d{1..3}e{1..3} > + // > + // root -> d -> 1 -> e -> 1 -> EMPTY > + // 2 // 2 // > + // 3 / 3 / > + > + // {1..3}{4..6} 14 15 16 24 25 26 34 35 36 > + // > + // root -> 1 -> 4 > + // 2 // 5 > + // 3 / 6 > + > + // we really expect that the first token is an open paren the > + // caller should have consumed the prefix before calling this > + if (*beg++ != '{') > + return false; > + > + // now fill in the middle, each child we create directly will > + // have a child pointer to the suffix node > + > + // all of the nodes in the list are children of `parent'. the > + // graph from nodes after the list are > + const char* mid = _rw_find_next_comma (beg, end); > + if (!mid) > + return false; // no comma, then no list > + > + // find the end of th list expression > + const char* eol = _rw_find_close_brace (mid, end); > + if (!eol) > + return false; // no list terminator > + > + // build a node for the suffix. > + _rw_brace_node* suffix = _C_build_anything (eol+1, end); > + if (!suffix) > + return false; // failed to parse end > + > + _rw_brace_node* first_child = 0; > + _rw_brace_node* final_child = 0; > + > + while (mid) { > + > + // create a child from whatever is between beg and end. that childs > + // next pointer will be the suffix we created above. > + _rw_brace_node* child = _C_build_anything (beg, mid); > + if (!child) { > + return false; > + } > + > + if (!first_child) > + first_child = child; > + > + // append new child to end of chain > + if (final_child) > + final_child->sibling_ = child; > + final_child = child; > + > + // the nex pointer for this child is the suffix > + > + // suffix is the suffix of the child expression > + while (child->child_) > + child = child->child_; > + child->child_ = suffix; > + > + beg = mid + 1; > + mid = _rw_find_next_comma (beg, eol); > + } > + > + // okay, we have a pointer to the last comma in the list. create an > + // item for the data between the comma and the list terminator > + > + // '{abc,d{1..3}e}a' > + // ^ ^ ^ > + // beg eol end > + > + // build nodes from the last entry in the list > + _rw_brace_node* child = _C_build_anything (beg, eol); > + if (!child) { > + return false; > + } > + > + // append last child to end of chain > + final_child->sibling_ = child; > + final_child = child; > + > + // suffix is the suffix of the child expression > + while (child->child_) > + child = child->child_; > + child->child_ = suffix; > + > + // success, return first child in this expansion > + return first_child; > +} > + > +bool _rw_brace_graph::_C_append (const char* s, int n) > +{ > + const int new_len = string_len_ + n; > + > + // not enough space, grow buf > + if (! (new_len < string_cap_)) { > + > + // buf grows in 256 byte blocks > + int new_cap = string_cap_; > + while (! (new_len < new_cap)) > + new_cap += 256; > + > + char* new_buf = (char*)malloc (new_cap); > + if (!new_buf) > + return false; > + > + // copy the old data > + memcpy (new_buf, string_buf_, string_len_); > + > + // copy the new data > + memcpy (new_buf + string_len_, s, n); > + new_buf [new_len] = '\0'; > + > + // don't free until after append because `s' may > + // be in string_buf_ > + if (string_buf_ != user_buf_) > + free (string_buf_); > + > + string_cap_ = new_cap; > + string_len_ = new_len; > + string_buf_ = new_buf; > + } > + > + // just copy the data > + else { > + memcpy (string_buf_ + string_len_, s, n); > + string_buf_ [new_len] = '\0'; > + > + string_len_ = new_len; > + } > + > + return true; > +} > + > + > +bool _rw_brace_graph::_C_brace_expand_write (_rw_recursion_context* context) > +{ > + if (context->parent_) { > + if (!_C_brace_expand_write (context->parent_)) > + return false; > + } > + > + // write the data at this level > + //return _C_append (context->node_->str_, context->node_->len_); > + > + bool is_escaped = false; > + > + const char* beg = context->node_->str_; > + for (int n = 0; n < context->node_->len_; ++n, ++beg) { > + > + is_escaped = !is_escaped && (*beg == '\\'); > + if (!is_escaped) { > + if (!_C_append (beg, 1)) > + return false; > + } > + } > + > + return true; > +} > + > +bool _rw_brace_graph::_C_brace_expand (_rw_recursion_context* self, char sep) > +{ > + // if this node has no children or siblings, we have found a full > + // expansion. > + if (!self->node_ || > + !self->node_->sibling_ && !self->node_->child_) { > + > + const int length_before = string_len_; > + > + // use recursion again to walk back to the root the graph and > + // write each contexts data as we unwind back toward the leaf > + if (!_C_brace_expand_write (self)) > + return false; > + > + const int length_after = string_len_; > + > + // don't write a seperator if we wrote no data > + if (length_before != length_after && !_C_append (&sep, 1)) > + return false; > + > + return true; > + } > + > + // iterate through all of the children of the node, thus finding all > + // other combinations > + _rw_recursion_context context (self); > + while (context.node_) { > + > + if (!_C_brace_expand (&context, sep)) > + return false; > + > + context.node_ = context.node_->sibling_; > + } > + > + return true; > +} > + > +// > +// returns 0 if brace_expr is not a valid brace expression, else a > +// pointer to the buf that stores the expanded expression. if the > +// returned value is not the same pointer as the input parameter > +// expanded, then the user must deallocate the pointer with a call > +// to free(). > +char* rw_brace_expand (const char* brace_expr, char* s, int n, int sep) > +{ > + if (!brace_expr) > + return 0; > + > + _rw_brace_graph graph; > + > + // build the graph, and then expand it into buf > + char* buf = graph._C_build_and_expand (brace_expr, s, n, sep); > + if (!buf) > + return 0; > + > + return buf; > +} > + > > >