/************************************************************************
 *
 * braceexp.cpp - definitions of rw_brace_expand and rw_shell_expand
 *
 * $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.
 * 
 **************************************************************************/

// expand _TEST_EXPORT macros
#define _RWSTD_TEST_SRC

#include <stdlib.h> // for malloc(), free()
#include <string.h> // for memcpy()
#include <ctype.h>  // for isspace()
#include <assert.h> // for assert()

#include <rw_braceexp.h>


// for convenience
typedef unsigned char UChar;


// search `beg' to `end' for a character that `fn'
// returns non-zero.
static const char*
_rw_find_match (const char* beg,
                const char* end,
                bool match_space)
{
    bool is_escaped = false;

    for (/**/; beg < end; ++beg) {

        const bool is_space = 0 != isspace (UChar (*beg));

        if (!is_escaped && match_space == is_space) {
            return beg;
        }

        is_escaped = !is_escaped && (*beg == '\\');
    }

    return 0;
}

// similar to sprintf (buffer, "%ld", value), but the output
// is not locale dependent. we choose not to use code from
// the test harness because we may need to move this around.
static int _rw_itoa_10 (char* buffer, long value)
{
    const bool neg = value < 0;

    if (neg)
        value = 0 - value;

    // write it out in reverse
    int n = 0;
    do {

        const long q = value / 10;
        const long r = value - (q * 10);
        value = q;

        switch (r)
        {
            case 0: buffer [n] = '0'; break;
            case 1: buffer [n] = '1'; break;
            case 2: buffer [n] = '2'; break;
            case 3: buffer [n] = '3'; break;
            case 4: buffer [n] = '4'; break;
            case 5: buffer [n] = '5'; break;
            case 6: buffer [n] = '6'; break;
            case 7: buffer [n] = '7'; break;
            case 8: buffer [n] = '8'; break;
            case 9: buffer [n] = '9'; break;
            default:                  break;
        }

        n += 1;

    } while (value != 0);

    // write the sign
    if (neg)
        buffer [n++] = '-';

    // then reverse it
    for (int i = 0, j = n - 1; i < j; ++i, --j)
    {
        const char c = buffer [i];
        buffer [i] = buffer [j];
        buffer [j] = c;
    }

    return n;
}


// 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.
//
// this function ignores escaped braces and those that look like they
// belong to a shell variable expansion. this is for consistency with
// bash. i.e. there is no open brace in a\{b\}c or a${b}c.
static const char* _rw_find_open_brace (const char* beg,
                                        const char* end)
{
    bool is_escaped = false;
    bool is_shelled = false;

    for (/**/; beg < end; ++beg) {

        const bool is_match = (*beg == '{');
        if (!is_escaped && !is_shelled && is_match) {
            return beg;
        }

        is_shelled = !is_shelled && (*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 < end; ++beg) {

        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 < end; ++beg) {

        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;
}

struct _rw_string_buffer
{
    _rw_string_buffer (char* s, size_t n)
        : capacity_ (n)
        , length_ (0)
        , buffer_ (s)
        , owned_ (false)
    {
    }

    // destructor does not deallocate memory
    // user expected to do that

    size_t capacity_;
    size_t length_;
    char* buffer_;
    bool  owned_;

    bool append (const char* s, size_t n);

private:
    // not implemented
    _rw_string_buffer (const _rw_string_buffer&);
    _rw_string_buffer& operator= (const _rw_string_buffer&);
};

// this is where most of the work is done.
struct _rw_brace_graph
{
    //
    _rw_brace_graph ();

    //
    ~_rw_brace_graph ();

    // expand brace expression from `beg' to `end' into `len' bytes of
    // `buf'. if it won't fit, we allocate a buffer with malloc() and
    // return that. so the caller needs to free() the return buffer if
    // it is not equal to `buf'.
    char* build_and_expand (const char* beg,
                            const char* end,
                            char* buf, size_t len, char sep);


private:

    // not implemented
    _rw_brace_graph (const _rw_brace_graph&);
    _rw_brace_graph& operator= (const _rw_brace_graph&);

    // node for a directed-acyclic-graph that we build from the original
    // brace expression
    struct _rw_brace_node
    {
        const char* str_;
        size_t      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.
    // and they are reused for every build_and_expand() call.
    _rw_brace_node* 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 sequence of tokens, or arbitrary literal text. escapes on commas
    // and braces are ignored, and left intact otherwise.
    _rw_brace_node* build_anything (const char* beg, const char* end);

    // generates a dag from an arbitrary sequence brace expression. the
    // format is `{?..?}suffix' where both ? are alphabetic characters
    // of the same character class [upper/lower].
    _rw_brace_node* build_character_sequence (const char* beg,
                                              const char* end);

    // generates a dag from an arbitrary sequence brace expression. the
    // format is `{?..?}suffix' where both ? are integer expressions.
    _rw_brace_node* build_integer_sequence (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 build_anything.
    _rw_brace_node* build_list     (const char* beg, const char* end);

    // the number of nodes held by each brace buffer [see below]
    enum { size = 64 };

#ifdef _RWSTD_NO_NESTED_CLASS_ACCESS

    // allow _rw_brace_node_buffer access to _rw_brace_graph's private
    // type(s) if the resolution of cwg issue 45 is not yet implemented
    struct _rw_brace_node_buffer;
    friend struct _rw_brace_node_buffer;

    // allow _rw_recursion_context access to _rw_brace_graph's private
    // type(s) if the resolution of cwg issue 45 is not yet implemented
    struct _rw_recursion_context;
    friend struct _rw_recursion_context;

#endif    // _RWSTD_NO_NESTED_CLASS_ACCESS

    // this is essentially a rope with a fixed length payload of
    // brace nodes
    struct _rw_brace_node_buffer
    {
        _rw_brace_node nodes_ [size];
        size_t         used_; // number of nodes_ used in this buffer
        _rw_brace_node_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 get_new_node() member.
    _rw_brace_node_buffer node_cache_;    
    _rw_brace_node_buffer* nodes_; // pointer to last allocated node buffer

    // code for handling integer ranges

    void reset_for_reuse (char* buf, size_t len);
    void free_range_buffers ();

    // this is essentially a rope with a variable length payload
    struct _rw_range_buffer
    {
        _rw_range_buffer* next_;
    };

    _rw_range_buffer* ranges_;

    // code for generating the string

    _rw_string_buffer string_;

    // 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* pnode)
            : parent_ (0), node_ (pnode)
        {
        }

        _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 brace_expand (_rw_recursion_context* self, char sep);

    // this function writes the data at each level of the dag
    // to our internal buffer.
    bool brace_expand_write (_rw_recursion_context* context);
};

_rw_brace_graph::_rw_brace_graph ()
    : nodes_ (&node_cache_)
    , ranges_ (0)
    , string_ (0, 0)
{
    node_cache_.next_ = 0;
}

_rw_brace_graph::~_rw_brace_graph ()
{
    _rw_brace_node_buffer* nodes = node_cache_.next_;
    while (nodes) {

        _rw_brace_node_buffer* next = nodes->next_;
        nodes->next_ = 0;

        // deallocate this buffer
        free (nodes);

        // setup to deallocate next one
        nodes = next;
    }

    reset_for_reuse (0, 0);
}


char*
_rw_brace_graph::build_and_expand (const char* beg,
                                   const char* end,
                                   char* buf, size_t len, char sep)
{
    assert (beg != 0);
    assert (end != 0);

    if (!beg || !end)
        return 0;

    // reset member data so we can reuse allocated buffers
    // if there are any
    reset_for_reuse (buf, len);

    _rw_brace_node* root
        = build_anything (beg, end);
    if (!root)
        return 0;

   // this helps us do the building of the output string
    _rw_recursion_context context (root);

    if (!brace_expand (&context, sep)) {
        if (string_.owned_)
            free (string_.buffer_);
        string_.buffer_ = 0;
    }

    // kill the last seperator with a null terminator
    else if (string_.buffer_) {
        const size_t pos = string_.length_ < 1 ? 0 : string_.length_ - 1;
        string_.buffer_ [pos] = '\0';
    }

    return string_.buffer_;
}

_rw_brace_graph::_rw_brace_node*
_rw_brace_graph::get_new_node ()
{
    nodes_->used_ += 1;

    // if we run out of space, move to the next buffer
    if (! (nodes_->used_ < size)) {

        // if we have got a buffer, reuse it
        if (nodes_->next_) {

            nodes_ = nodes_->next_;
        }

        // otherwise we allocate one
        else {

            const size_t sz = sizeof (_rw_brace_node_buffer);

            nodes_->next_ = (_rw_brace_node_buffer*)malloc (sz);
            if (!nodes_->next_)
                return 0;

            nodes_ = nodes_->next_;
            nodes_->next_ = 0;
        }

        nodes_->used_ = 1;
    }

    _rw_brace_node* node = &nodes_->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::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 = get_new_node ();
        if (!prefix)
            return 0;
              
        prefix->str_ = beg;
        prefix->len_ = (open_brace - beg);

        _rw_brace_node* child = 0;
        
        // try to build a character sequence expansion like {a..g}
        child = build_character_sequence (open_brace, end);
        if (!child) {

            // try to do an integer sequence expansion like {-19..+72}
            child = build_integer_sequence (open_brace, end);
            if (!child) {

                // try to do a list expansion like {a,b,cd}
                child = build_list (open_brace, end);
                if (!child) {

                    // we can't figure out what to do, so we fail
                    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 = get_new_node ();
    if (!prefix)
        return 0;

    prefix->str_ = beg;
    prefix->len_ = beg < end ? (end - beg) : 0;

    return prefix;
}

_rw_brace_graph::_rw_brace_node*
_rw_brace_graph::build_integer_sequence (const char* beg, const char* end)
{
    // check for {-10..100} type sequence expression. make sure not to
    // reference past the end of the string.
    if (*beg++ != '{')
        return 0;

    // this should point to first character after the integer value
    char* pend;

    // parse the first integer
    long ibeg = strtol (beg, &pend, 10);
    if (!ibeg && (pend == beg))
        return 0; // failed to parse an integer value

    // number of characters needed to represent ibeg
    const size_t ibeg_dig = (pend - beg);

    // make sure we have two dots
    beg = pend;
    if (! (beg [0] == '.' && beg [1] == '.'))
        return 0;

    // skip the two dots
    beg += 2;

    // parse the second integer
    long iend = strtol (beg, &pend, 10);
    if (!iend && (pend == beg))
        return 0; // failed to parse an integer value

    // number of characters needed to represent iend
    const size_t iend_dig = (pend - beg);

    // make sure we have an end brace
    beg = pend;
    if (beg [0] != '}')
        return 0;
    beg += 1;

    // build the suffix
    _rw_brace_node* suffix = build_anything (beg, end);
    if (!suffix)
        return 0; // failed to parse suffix

    // direction the range goes, +1 for increasing, -1 for decreasing
    const int dir = (ibeg < iend) ? 1 : -1;

    // maximum length of the string representation of a single
    // integer in the range
    const size_t len = (ibeg_dig < iend_dig ? iend_dig : ibeg_dig);

    // number of integers in the range [ibeg, iend]
    const size_t num = 1 + (iend - ibeg) * dir;

    // maximum number of bytes needed to represent all of the numbers
    // and a single null
    const size_t cnt = 1 + (num * len);

    // number of bytes we have to allocate, cnt of which is data
    // and the rest is to allow us to chain these buffers together
    const size_t bsz = cnt + sizeof (_rw_range_buffer);

    // allocate a rope segment big enough for all of the strings
    // we need to keep.
    _rw_range_buffer* buffer
        = (_rw_range_buffer*)malloc (bsz);
    if (!buffer)
        return 0;

    // add buffer to our list so we can free it later
    buffer->next_ = ranges_;
    ranges_ = buffer;

    // pointer to the current write position in the buffer
    char* ranges = (char*)&buffer [1];

    _rw_brace_node* first_child = 0;
    _rw_brace_node* final_child = 0;

    // build a list of children, associate each with suffix
    for (/**/; ibeg != iend; ibeg += 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 = get_new_node ();
        if (!child)
            return 0;

        // add a representation of cbeg to the ranges buffer
        child->len_ = _rw_itoa_10 (ranges, ibeg);
        child->str_ = ranges;

        // step past number of written characters
        ranges += child->len_;

        // 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 sequence.
    _rw_brace_node* child = get_new_node ();
    if (!child)
        return 0;

    // add a representation of cbeg to the ranges buffer
    child->len_ = _rw_itoa_10 (ranges, ibeg);
    child->str_ = ranges;

    // 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::build_character_sequence (const char* beg, const char* end)
{
    // check for {a..z} type sequence 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 sequence
    char cbeg = beg [1];
    char cend = beg [4];

    // only works if sequence characters are both lowercase or uppercase.
    const int both_are_lower =
        islower (UChar (cbeg)) && islower (UChar (cend));
    const int both_are_upper =
        isupper (UChar (cbeg)) && isupper (UChar (cend));

    if (! (both_are_lower || both_are_upper))
        return 0;

    // these must live for duration of program
    static const char* alpha_table [] =
    {
        "abcdefghijklmnopqrstuvwxyz",
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    };

    const char* sequence = alpha_table [both_are_upper];

    const int dir = (cbeg < cend) ? 1 : -1;

    // build the suffix
    _rw_brace_node* suffix = build_anything (beg + 6, end);
    if (!suffix)
        return 0; // 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 = get_new_node ();
        if (!child)
            return 0;

        // this finds beg in our array, we could have used strchr
        child->str_ = sequence + (cbeg - sequence [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 sequence.
    _rw_brace_node* child = get_new_node ();
    if (!child)
        return 0;

    child->str_ = sequence + (cbeg - sequence [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::build_list (const char* beg, const char* end)
{
    // 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

    // special case {}?

    // find the end of the brace list
    const char* end_of_list = _rw_find_close_brace (beg, end);
    if (!end_of_list)
        return false; // no list terminator

    // build a node for the suffix.
    _rw_brace_node* suffix = build_anything (end_of_list + 1, end);
    if (!suffix)
        return false; // failed to parse end

    // find the end of the first comma seperated token
    const char* mid = _rw_find_next_comma (beg, end_of_list);

    _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 = 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, end_of_list);
    }

    // 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 = build_anything (beg, end_of_list);
    if (!child)
        return false;

    if (!first_child)
        first_child = child;

    if (final_child)
        final_child->sibling_ = child;
    final_child = child;

    while (child->child_)
        child = child->child_;
    child->child_ = suffix;

    // success, return first child in this expansion
    return first_child;
}

void _rw_brace_graph::reset_for_reuse (char* buf, size_t len)
{
    node_cache_.used_ = 0;
    nodes_ = &node_cache_;

    string_.buffer_   = buf;
    string_.capacity_ = len;
    string_.length_   = 0;

    // we free these buffers because the size of the buffer
    // depends on the expression we are evaluating
    free_range_buffers ();
}

void _rw_brace_graph::free_range_buffers ()
{
    _rw_range_buffer* ranges = ranges_;
    while (ranges) {

        _rw_range_buffer* next = ranges->next_;
        ranges->next_ = 0;

        free (ranges);

        ranges = next;
    }

    ranges_ = 0;
}


bool _rw_brace_graph::brace_expand_write (_rw_recursion_context* context)
{
    if (context->parent_) {
        if (!brace_expand_write (context->parent_))
            return false;
    }

    bool is_escaped = false;

    const char* beg = context->node_->str_;
    const size_t len = context->node_->len_;

    for (size_t n = 0; n < len; ++n, ++beg) {

        is_escaped = !is_escaped && (*beg == '\\');
        if (!is_escaped) {
            if (!string_.append (beg, 1))
                return false;
        }
    }

    return true;
}

bool _rw_brace_graph::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 size_t length_before = string_.length_;

        // use recursion again to walk back to the root the graph and
        // write each contexts data as we unwind back toward the leaf
        if (!brace_expand_write (self))
            return false;

        const size_t length_after = string_.length_;

        // don't write a seperator if we wrote no data
        if (length_before != length_after && !string_.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 (!brace_expand (&context, sep))
            return false;

        context.node_ = context.node_->sibling_;
    }

    return true;
}

bool _rw_string_buffer::append (const char* s, size_t n)
{
    const size_t new_len = length_ + n;

    // not enough space, grow buf
    if (! (new_len < capacity_)) {

        // buf grows in 256 byte blocks
        size_t new_cap = capacity_;
        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, buffer_, length_);

        // copy the new data
        memcpy (new_buf + length_, s, n);
        new_buf [new_len] = '\0';

        // don't free until after append because `s' may
        // be in string_buf_
        if (owned_)
            free (buffer_);

        capacity_ = new_cap;
        length_   = new_len;
        buffer_   = new_buf;
        owned_    = true;
    }

    // just copy the data
    else {
        memcpy (buffer_ + length_, s, n);
        buffer_ [new_len] = '\0';
        length_ = new_len;
    }

    return true;
}

//
char* rw_brace_expand (const char* brace_expr,
                       size_t sz,
                       char* s, size_t n, char sep)
{
    if (!brace_expr)
        return 0;

    // if the length isn't provided, assume entire string
    if (!sz)
        sz = strlen (brace_expr);

    _rw_brace_graph graph;

    // build the graph, and then expand it into buf
    char* buf = graph.build_and_expand (brace_expr,
                                        brace_expr + sz, s, n, sep);
    if (!buf)
        return 0;

    return buf;
}


//
char* rw_shell_expand (const char* shell_expr, size_t sz,
                       char* s, size_t n, char sep)
{
    if (!shell_expr)
        return 0;

    // if the length isn't provided, assume entire string
    if (!sz)
        sz = strlen (shell_expr);

    // assume shell_expr is null terminated
    const char* beg = shell_expr;
    const char* end = shell_expr + sz;

    // helper for output
    _rw_string_buffer result (s, n);

    // helper for expanding braces
    _rw_brace_graph graph;

    // first non-whitespace character
    const char* tok_beg = _rw_find_match (beg, end, false);
    if (!tok_beg) {

        if (!result.append ("\0", 1))
            return 0;

        return result.buffer_;
    }

    bool is_first_expand = true;

    while (tok_beg)
    {
        // first whitespace character
        const char* tok_end = _rw_find_match (tok_beg, end, true);
        if (!tok_end)
            tok_end = end;

        // expand from tok_beg to tok_end into buf
        char buf [256];

        char* exp =
            graph.build_and_expand (tok_beg, tok_end, buf, sizeof (buf), sep);

        // apptok_end space, then expansion, expansion

        bool app = false;

        if (exp) {

            // in case user uses a null seperator
            const char* term = exp;
            for (/**/; *term; term += strlen (term) + 1)
                ;

            const size_t len = exp < term ? (term - exp) - 1 : 0;
        
            if (is_first_expand)
                app = result.append (exp, len);
            else if (result.append (&sep, 1))
                app = result.append (exp, len);
        }

        is_first_expand = false;

        if (exp != buf)
            free (exp);

        // if we didn't append, or we failed to append
        // then this function fails
        if (!app) {

            if (result.owned_)
                free (result.buffer_);

            return 0;
        }

        // bail if we're at the end of string
        if (!tok_end)
            break;

        // fid next nonwhitespace, which is the start of the next token
        tok_beg = _rw_find_match (tok_end, end, false);
    }

    return result.buffer_;
}