stdcxx-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From vi...@apache.org
Subject svn commit: r628611 - in /stdcxx/trunk/tests: include/rw_braceexp.h self/0.braceexp.cpp src/braceexp.cpp
Date Mon, 18 Feb 2008 04:35:16 GMT
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  <vitek@roguewave.com>

	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 <testdefs.h>
+
+
+// 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 <rw_braceexp.h>
+
+#include <stdio.h>        // for fprintf(), stderr
+#include <stdlib.h>       // for free()
+#include <string.h>       // 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 <stdlib.h>
+#include <string.h>
+
+
+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;
+}
+



Mime
View raw message