stdcxx-dev mailing list archives

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