EIC code displayed by LXR master/​include/​boost/​wave/​util/​flex_string.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:53:42

 /*=============================================================================
     Boost.Wave: A Standard compliant C++ preprocessor library
     http://www.boost.org/
 
     Copyright (c) 2001 by Andrei Alexandrescu. Distributed under the Boost
     Software License, Version 1.0. (See accompanying file
     LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 =============================================================================*/
 
 // This code is taken from:
 // Andrei Alexandrescu, Generic<Programming>: A Policy-Based basic_string
 // Implementation. http://www.cuj.com/documents/s=7994/cujcexp1906alexandr/
 //
 // #HK030306:
 //      - Moved into the namespace boost::wave::util
 //      - Added a bunch of missing typename(s)
 //      - Integrated with boost config
 //      - Added a missing header include
 //      - Added special constructors and operator= to allow CowString to be
 //        a real COW-string (removed unnecessary data copying)
 //      - Fixed a string terminating bug in append
 //
 // #HK040109:
 //      - Incorporated the changes from Andrei's latest version of this class
 //
 // #HK070307:
 //      - Once again incorporated the changes from Andrei's latest version of
 //        this class
 //
 // #HK090523:
 //      - Incorporated the changes from latest version of flex_string as
 //        maintained in Loki
 //
 // #HK130910:
 //      - Removed the getline implementation which was borrowed from the SGI
 //        STL as the license for this code is not compatible with Boost.
 
 #ifndef BOOST_FLEX_STRING_INC_
 #define BOOST_FLEX_STRING_INC_
 
 /*
 ////////////////////////////////////////////////////////////////////////////////
 template <typename E, class A = @>
 class StoragePolicy
 {
     typedef E value_type;
     typedef @ iterator;
     typedef @ const_iterator;
     typedef A allocator_type;
     typedef @ size_type;
 
     StoragePolicy(const StoragePolicy& s);
     StoragePolicy(const A&);
     StoragePolicy(const E* s, size_type len, const A&);
     StoragePolicy(size_type len, E c, const A&);
     ~StoragePolicy();
 
     iterator begin();
     const_iterator begin() const;
     iterator end();
     const_iterator end() const;
 
     size_type size() const;
     size_type max_size() const;
     size_type capacity() const;
 
     void reserve(size_type res_arg);
 
     void append(const E* s, size_type sz);
 
     template <class InputIterator>
     void append(InputIterator b, InputIterator e);
 
     void resize(size_type newSize, E fill);
 
     void swap(StoragePolicy& rhs);
 
     const E* c_str() const;
     const E* data() const;
 
     A get_allocator() const;
 };
 ////////////////////////////////////////////////////////////////////////////////
 */
 
 #include <boost/config.hpp>
 #include <boost/assert.hpp>
 #include <boost/throw_exception.hpp>
 
 #include <boost/core/allocator_access.hpp>
 #include <boost/iterator/reverse_iterator.hpp>
 
 #include <boost/wave/wave_config.hpp>
 #if BOOST_WAVE_SERIALIZATION != 0
 #include <boost/serialization/serialization.hpp>
 #include <boost/serialization/split_free.hpp>
 #include <boost/serialization/collections_save_imp.hpp>
 #include <boost/serialization/collections_load_imp.hpp>
 #define BOOST_WAVE_FLEX_STRING_SERIALIZATION_HACK 1
 #endif
 
 #include <memory>
 #include <new>
 #include <vector>
 #include <algorithm>
 #include <functional>
 #include <limits>
 #include <stdexcept>
 #include <ios>
 
 #include <cstddef>
 #include <cstring>
 #include <cstdlib>
 
 // this must occur after all of the includes and before any code appears
 #ifdef BOOST_HAS_ABI_HEADERS
 #include BOOST_ABI_PREFIX
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
 namespace boost {
 namespace wave {
 namespace util {
 
 namespace flex_string_details
 {
     template <class InIt, class OutIt>
     OutIt copy_n(InIt b,
         typename std::iterator_traits<InIt>::difference_type n, OutIt d)
     {
         for (/**/; n != 0; --n, ++b, ++d)
         {
             *d = *b;
         }
         return d;
     }
 
     template <class Pod, class T>
     inline void pod_fill(Pod* b, Pod* e, T c)
     {
         switch ((e - b) & 7)
         {
         case 0:
             while (b != e)
             {
                 *b = c; ++b; BOOST_FALLTHROUGH;
         case 7: *b = c; ++b; BOOST_FALLTHROUGH;
         case 6: *b = c; ++b; BOOST_FALLTHROUGH;
         case 5: *b = c; ++b; BOOST_FALLTHROUGH;
         case 4: *b = c; ++b; BOOST_FALLTHROUGH;
         case 3: *b = c; ++b; BOOST_FALLTHROUGH;
         case 2: *b = c; ++b; BOOST_FALLTHROUGH;
         case 1: *b = c; ++b;
             }
         }
     }
 
     template <class Pod>
     inline void pod_move(const Pod* b, const Pod* e, Pod* d)
     {
         using namespace std;
         memmove(d, b, (e - b) * sizeof(*b));
     }
 
     template <class Pod>
     inline Pod* pod_copy(const Pod* b, const Pod* e, Pod* d)
     {
         const std::size_t s = e - b;
         using namespace std;
         memcpy(d, b, s * sizeof(*b));
         return d + s;
     }
 
     template <typename T> struct get_unsigned
     {
         typedef T result;
     };
 
     template <> struct get_unsigned<char>
     {
         typedef unsigned char result;
     };
 
     template <> struct get_unsigned<signed char>
     {
         typedef unsigned char result;
     };
 
     template <> struct get_unsigned<short int>
     {
         typedef unsigned short int result;
     };
 
     template <> struct get_unsigned<int>
     {
         typedef unsigned int result;
     };
 
     template <> struct get_unsigned<long int>
     {
         typedef unsigned long int result;
     };
 
     enum Shallow {};
 }
 
 template <class T> class mallocator
 {
 public:
     typedef T                 value_type;
     typedef value_type*       pointer;
     typedef const value_type* const_pointer;
     typedef value_type&       reference;
     typedef const value_type& const_reference;
     typedef std::size_t       size_type;
     //typedef unsigned int      size_type;
     //typedef std::ptrdiff_t    difference_type;
     typedef int               difference_type;
 
     template <class U>
     struct rebind { typedef mallocator<U> other; };
 
     mallocator() {}
     mallocator(const mallocator&) {}
     //template <class U>
     //mallocator(const mallocator<U>&) {}
     ~mallocator() {}
 
     pointer address(reference x) const { return &x; }
     const_pointer address(const_reference x) const
     {
         return x;
     }
 
     pointer allocate(size_type n, const_pointer = 0)
     {
         using namespace std;
         void* p = malloc(n * sizeof(T));
         if (!p) boost::throw_exception(std::bad_alloc());
         return static_cast<pointer>(p);
     }
 
     void deallocate(pointer p, size_type)
     {
         using namespace std;
         free(p);
     }
 
     size_type max_size() const
     {
         return static_cast<size_type>(-1) / sizeof(T);
     }
 
     void construct(pointer p, const value_type& x)
     {
         new(p) value_type(x);
     }
 
     void destroy(pointer p)
     {
         p->~value_type();
     }
 
 private:
     void operator=(const mallocator&);
 };
 
 template<> class mallocator<void>
 {
   typedef void        value_type;
   typedef void*       pointer;
   typedef const void* const_pointer;
 
   template <class U>
   struct rebind { typedef mallocator<U> other; };
 };
 
 template <class T>
 inline bool operator==(const mallocator<T>&,
                        const mallocator<T>&) {
   return true;
 }
 
 template <class T>
 inline bool operator!=(const mallocator<T>&,
                        const mallocator<T>&) {
   return false;
 }
 
 #if defined(BOOST_GCC) && BOOST_GCC >= 40700
 // gcc 11.2 fails to deduce below that pData_ never points to emptyString_ if capacity() == 0 and emits warnings like these:
 // 'operator delete(void*, unsigned long)' called on unallocated object 'boost::wave::util::SimpleStringStorage<char, std::allocator<char> >::emptyString_' [-Wfree-nonheap-object]
 // Unfortunately, suppressing this warning doesn't work, so we have to use __builtin_unreachable() to assert that this never happens.
 // __builtin_unreachable is supported since gcc 4.6, -Wfree-nonheap-object is supported since 4.7.
 #define BOOST_WAVE_COMPILE_TIME_ASSERT(x) if (!(x)) __builtin_unreachable()
 #else
 #define BOOST_WAVE_COMPILE_TIME_ASSERT(x)
 #endif
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template SimpleStringStorage
 // Allocates memory with malloc
 ////////////////////////////////////////////////////////////////////////////////
 
 template <typename E, class A = std::allocator<E> >
 class SimpleStringStorage
 {
     // The "public" below exists because MSVC can't do template typedefs
 public:
     struct Data
     {
         Data() : pEnd_(buffer_), pEndOfMem_(buffer_) { buffer_[0] = E(0); }
 
         E* pEnd_;
         E* pEndOfMem_;
         E buffer_[1];
     };
     static const Data emptyString_;
 
     typedef typename boost::allocator_size_type<A>::type size_type;
 
 private:
     Data* pData_;
 
     void Init(size_type size, size_type capacity)
     {
         BOOST_ASSERT(size <= capacity);
         if (capacity == 0)
         {
             pData_ = const_cast<Data*>(&emptyString_);
         }
         else
         {
             // 11-17-2000: comment added:
             //     No need to allocate (capacity + 1) to
             //     accommodate the terminating 0, because Data already
             //     has one character in there
             pData_ = static_cast<Data*>(
                 malloc(sizeof(Data) + capacity * sizeof(E)));
             if (!pData_) boost::throw_exception(std::bad_alloc());
             pData_->pEnd_ = pData_->buffer_ + size;
             pData_->pEndOfMem_ = pData_->buffer_ + capacity;
         }
     }
 
 private:
     // Warning - this doesn't initialize pData_. Used in reserve()
     SimpleStringStorage()
     { }
 
 public:
     typedef E value_type;
     typedef E* iterator;
     typedef const E* const_iterator;
     typedef A allocator_type;
 
     SimpleStringStorage(const SimpleStringStorage& rhs)
     {
         const size_type sz = rhs.size();
         Init(sz, sz);
         if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.end(), begin());
     }
 
     SimpleStringStorage(const SimpleStringStorage& s,
         flex_string_details::Shallow)
         : pData_(s.pData_)
     {
     }
 
     SimpleStringStorage(const A&)
     { pData_ = const_cast<Data*>(&emptyString_); }
 
     SimpleStringStorage(const E* s, size_type len, const A&)
     {
         Init(len, len);
         flex_string_details::pod_copy(s, s + len, begin());
     }
 
     SimpleStringStorage(size_type len, E c, const A&)
     {
         Init(len, len);
         flex_string_details::pod_fill(begin(), end(), c);
     }
 
     SimpleStringStorage& operator=(const SimpleStringStorage& rhs)
     {
         const size_type sz = rhs.size();
         reserve(sz);
         flex_string_details::pod_copy(&*rhs.begin(), &*rhs.end(), begin());
         pData_->pEnd_ = &*begin() + sz;
         return *this;
     }
 
     ~SimpleStringStorage()
     {
         BOOST_ASSERT(begin() <= end());
         if (capacity() > 0)
         {
             BOOST_WAVE_COMPILE_TIME_ASSERT(pData_ != &emptyString_);
             free(pData_);
         }
     }
 
     iterator begin()
     { return pData_->buffer_; }
 
     const_iterator begin() const
     { return pData_->buffer_; }
 
     iterator end()
     { return pData_->pEnd_; }
 
     const_iterator end() const
     { return pData_->pEnd_; }
 
     size_type size() const
     { return pData_->pEnd_ - pData_->buffer_; }
 
     size_type max_size() const
     { return std::size_t(-1) / sizeof(E) - sizeof(Data) - 1; }
 
     size_type capacity() const
     { return pData_->pEndOfMem_ - pData_->buffer_; }
 
     void reserve(size_type res_arg)
     {
         size_type cap = capacity();
         if (res_arg <= cap)
         {
             // @@@ insert shrinkage here if you wish
             return;
         }
 
         if (cap == 0)
         {
             Init(0, res_arg);
         }
         else
         {
             const size_type sz = size();
 
             void* p = realloc(pData_,
                 sizeof(Data) + res_arg * sizeof(E));
             if (!p) boost::throw_exception(std::bad_alloc());
 
             if (p != pData_)
             {
                 pData_ = static_cast<Data*>(p);
                 pData_->pEnd_ = pData_->buffer_ + sz;
             }
             pData_->pEndOfMem_ = pData_->buffer_ + res_arg;
         }
     }
 
     void append(const E* s, size_type sz)
     {
         const size_type neededCapacity = size() + sz;
 
         if (capacity() < neededCapacity)
         {
             const iterator b = begin();
             static std::less_equal<const E*> le;
             if (le(b, s) && le(s, end()))
             {
                // aliased
                 const size_type offset = s - b;
                 reserve(neededCapacity);
                 s = begin() + offset;
             }
             else
             {
                 reserve(neededCapacity);
             }
         }
         flex_string_details::pod_copy(s, s + sz, end());
         pData_->pEnd_ += sz;
     }
 
     template <class InputIterator>
     void append(InputIterator b, InputIterator e)
     {
         // @@@ todo: optimize this depending on iterator type
         for (; b != e; ++b)
         {
             *this += *b;
         }
     }
 
     void resize(size_type newSize, E fill)
     {
         const int delta = int(newSize - size());
         if (delta == 0) return;
 
         if (delta > 0)
         {
             if (newSize > capacity())
             {
                 reserve(newSize);
             }
             E* e = &*end();
             flex_string_details::pod_fill(e, e + delta, fill);
         }
         pData_->pEnd_ = pData_->buffer_ + newSize;
     }
 
     void swap(SimpleStringStorage& rhs)
     {
         std::swap(pData_, rhs.pData_);
     }
 
     const E* c_str() const
     {
         if (capacity() > 0) *pData_->pEnd_ = E();
         return pData_->buffer_;
     }
 
     const E* data() const
     { return pData_->buffer_; }
 
     A get_allocator() const
     { return A(); }
 };
 
 template <typename E, class A>
 const typename SimpleStringStorage<E, A>::Data
 SimpleStringStorage<E, A>::emptyString_ =
     typename SimpleStringStorage<E, A>::Data();
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template AllocatorStringStorage
 // Allocates with your allocator
 // Takes advantage of the Empty Base Optimization if available
 ////////////////////////////////////////////////////////////////////////////////
 
 template <typename E, class A = std::allocator<E> >
 class AllocatorStringStorage : public A
 {
     typedef typename boost::allocator_size_type<A>::type size_type;
     typedef typename SimpleStringStorage<E, A>::Data Data;
 
     void* Alloc(size_type sz, const void* p = 0)
     {
         return boost::allocator_allocate(static_cast<A&>(*this), 1 + (sz - 1) / sizeof(E),
             static_cast<const char*>(p));
     }
 
     void Free(void* p, size_type sz)
     {
         boost::allocator_deallocate(static_cast<A&>(*this), static_cast<E*>(p), sz);
     }
 
     Data* pData_;
 
     void Init(size_type size, size_type cap)
     {
         BOOST_ASSERT(size <= cap);
 
         if (cap == 0)
         {
             pData_ = const_cast<Data*>(
                 &SimpleStringStorage<E, A>::emptyString_);
         }
         else
         {
             pData_ = static_cast<Data*>(Alloc(
                 cap * sizeof(E) + sizeof(Data)));
             pData_->pEnd_ = pData_->buffer_ + size;
             pData_->pEndOfMem_ = pData_->buffer_ + cap;
         }
     }
 
 public:
     typedef E value_type;
     typedef E* iterator;
     typedef const E* const_iterator;
     typedef A allocator_type;
 
     AllocatorStringStorage()
     : A(), pData_(0)
     {
     }
 
     AllocatorStringStorage(const AllocatorStringStorage& rhs)
     : A(rhs.get_allocator())
     {
         const size_type sz = rhs.size();
         Init(sz, sz);
         if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.end(), begin());
     }
 
     AllocatorStringStorage(const AllocatorStringStorage& s,
         flex_string_details::Shallow)
     : A(s.get_allocator())
     {
         pData_ = s.pData_;
     }
 
     AllocatorStringStorage(const A& a) : A(a)
     {
         pData_ = const_cast<Data*>(
             &SimpleStringStorage<E, A>::emptyString_);
     }
 
     AllocatorStringStorage(const E* s, size_type len, const A& a)
     : A(a)
     {
         Init(len, len);
         flex_string_details::pod_copy(s, s + len, begin());
     }
 
     AllocatorStringStorage(size_type len, E c, const A& a)
     : A(a)
     {
         Init(len, len);
         flex_string_details::pod_fill(&*begin(), &*end(), c);
     }
 
     AllocatorStringStorage& operator=(const AllocatorStringStorage& rhs)
     {
         const size_type sz = rhs.size();
         reserve(sz);
         flex_string_details::pod_copy(&*rhs.begin(), &*rhs.end(), begin());
         pData_->pEnd_ = &*begin() + rhs.size();
         return *this;
     }
 
     ~AllocatorStringStorage()
     {
         if (capacity())
         {
             BOOST_WAVE_COMPILE_TIME_ASSERT(pData_ != (&SimpleStringStorage<E, A>::emptyString_));
             Free(pData_,
                 sizeof(Data) + capacity() * sizeof(E));
         }
     }
 
     iterator begin()
     { return pData_->buffer_; }
 
     const_iterator begin() const
     { return pData_->buffer_; }
 
     iterator end()
     { return pData_->pEnd_; }
 
     const_iterator end() const
     { return pData_->pEnd_; }
 
     size_type size() const
     { return size_type(end() - begin()); }
 
     size_type max_size() const
     { return boost::allocator_max_size(static_cast<const A&>(*this)); }
 
     size_type capacity() const
     { return size_type(pData_->pEndOfMem_ - pData_->buffer_); }
 
     void resize(size_type n, E c)
     {
         reserve(n);
         iterator newEnd = begin() + n;
         iterator oldEnd = end();
         if (newEnd > oldEnd)
         {
             // Copy the characters
             flex_string_details::pod_fill(oldEnd, newEnd, c);
         }
         if (capacity()) pData_->pEnd_ = newEnd;
     }
 
     void reserve(size_type res_arg)
     {
         if (res_arg <= capacity())
         {
             // @@@ shrink to fit here
             return;
         }
 
         A& myAlloc = *this;
         AllocatorStringStorage newStr(myAlloc);
         newStr.Init(size(), res_arg);
 
         flex_string_details::pod_copy(begin(), end(), newStr.begin());
 
         swap(newStr);
     }
 
     template <class ForwardIterator>
     void append(ForwardIterator b, ForwardIterator e)
     {
         const size_type
             sz = std::distance(b, e),
             neededCapacity = size() + sz;
 
         if (capacity() < neededCapacity)
         {
 //             typedef std::less_equal<const E*> le_type;
 //             BOOST_ASSERT(!(le_type()(begin(), &*b) && le_type()(&*b, end())));
             reserve(neededCapacity);
         }
         std::copy(b, e, end());
         pData_->pEnd_ += sz;
     }
 
     void swap(AllocatorStringStorage& rhs)
     {
         // @@@ The following line is commented due to a bug in MSVC
         //std::swap(lhsAlloc, rhsAlloc);
         std::swap(pData_, rhs.pData_);
     }
 
     const E* c_str() const
     {
         if (capacity() > 0)
         {
             *pData_->pEnd_ = E();
         }
         return &*begin();
     }
 
     const E* data() const
     { return &*begin(); }
 
     A get_allocator() const
     { return *this; }
 };
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template VectorStringStorage
 // Uses std::vector
 // Takes advantage of the Empty Base Optimization if available
 ////////////////////////////////////////////////////////////////////////////////
 
 template <typename E, class A = std::allocator<E> >
 class VectorStringStorage : protected std::vector<E, A>
 {
     typedef std::vector<E, A> base;
 
 public: // protected:
     typedef E value_type;
     typedef typename base::iterator iterator;
     typedef typename base::const_iterator const_iterator;
     typedef A allocator_type;
     typedef typename boost::allocator_size_type<A>::type size_type;
 
     VectorStringStorage(const VectorStringStorage& s) : base(s)
     { }
 
     VectorStringStorage(const A& a) : base(1, E(), a)
     { }
 
     VectorStringStorage(const E* s, size_type len, const A& a)
     : base(a)
     {
         base::reserve(len + 1);
         base::insert(base::end(), s, s + len);
         // Terminating zero
         base::insert(base::end(), E());
     }
 
     VectorStringStorage(size_type len, E c, const A& a)
     : base(len + 1, c, a)
     {
         // Terminating zero
         base::back() = E();
     }
 
     VectorStringStorage& operator=(const VectorStringStorage& rhs)
     {
         base& v = *this;
         v = rhs;
         return *this;
     }
 
     iterator begin()
     { return base::begin(); }
 
     const_iterator begin() const
     { return base::begin(); }
 
     iterator end()
     { return base::end() - 1; }
 
     const_iterator end() const
     { return base::end() - 1; }
 
     size_type size() const
     { return base::size() - 1; }
 
     size_type max_size() const
     { return base::max_size() - 1; }
 
     size_type capacity() const
     { return base::capacity() - 1; }
 
     void reserve(size_type res_arg)
     {
         BOOST_ASSERT(res_arg < max_size());
         base::reserve(res_arg + 1);
     }
 
     void append(const E* s, size_type sz)
     {
         // Check for aliasing because std::vector doesn't do it.
         static std::less_equal<const E*> le;
         if (!base::empty())
         {
             const E* start = &base::front();
             if (le(start, s) && le(s, start + size()))
             {
                 // aliased
                 const size_type offset = s - start;
                 reserve(size() + sz);
                 s = &base::front() + offset;
             }
         }
         base::insert(end(), s, s + sz);
     }
 
     template <class InputIterator>
     void append(InputIterator b, InputIterator e)
     {
         base::insert(end(), b, e);
     }
 
     void resize(size_type n, E c)
     {
         base::reserve(n + 1);
         base::back() = c;
         base::resize(n + 1, c);
         base::back() = E();
     }
 
     void swap(VectorStringStorage& rhs)
     { base::swap(rhs); }
 
     const E* c_str() const
     { return &*begin(); }
 
     const E* data() const
     { return &*begin(); }
 
     A get_allocator() const
     { return base::get_allocator(); }
 };
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template SmallStringOpt
 // Builds the small string optimization over any other storage
 ////////////////////////////////////////////////////////////////////////////////
 
 template <class Storage, unsigned int threshold,
     typename Align = typename Storage::value_type*>
 class SmallStringOpt
 {
 public:
     typedef typename Storage::value_type value_type;
     typedef value_type* iterator;
     typedef const value_type* const_iterator;
     typedef typename Storage::allocator_type allocator_type;
     typedef typename boost::allocator_size_type<allocator_type>::type size_type;
 
 private:
   enum { temp1 = threshold * sizeof(value_type) > sizeof(Storage)
         ? threshold  * sizeof(value_type)
         : sizeof(Storage) };
 
     enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };
 
 public:
     enum { maxSmallString =
     (temp2 + sizeof(value_type) - 1) / sizeof(value_type) };
 
 private:
     enum { magic = maxSmallString + 1 };
 
     union
     {
         mutable value_type buf_[maxSmallString + 1];
         Align align_;
     };
 
     Storage& GetStorage()
     {
         BOOST_ASSERT(buf_[maxSmallString] == magic);
         Storage* p = reinterpret_cast<Storage*>(&buf_[0]);
         return *p;
     }
 
     const Storage& GetStorage() const
     {
         BOOST_ASSERT(buf_[maxSmallString] == magic);
         const Storage *p = reinterpret_cast<const Storage*>(&buf_[0]);
         return *p;
     }
 
     bool Small() const
     {
         return buf_[maxSmallString] != magic;
     }
 
 public:
   SmallStringOpt(const SmallStringOpt& s)
     {
         if (s.Small())
         {
             flex_string_details::pod_copy(
                 s.buf_,
                 s.buf_ + s.size(),
                 buf_);
         }
         else
         {
             new(buf_) Storage(s.GetStorage());
         }
         buf_[maxSmallString] = s.buf_[maxSmallString];
     }
 
     SmallStringOpt(const allocator_type&)
     {
         buf_[maxSmallString] = maxSmallString;
     }
 
     SmallStringOpt(const value_type* s, size_type len, const allocator_type& a)
     {
         if (len <= maxSmallString)
         {
             flex_string_details::pod_copy(s, s + len, buf_);
             buf_[maxSmallString] = value_type(maxSmallString - len);
         }
         else
         {
             new(buf_) Storage(s, len, a);
             buf_[maxSmallString] = magic;
         }
     }
 
     SmallStringOpt(size_type len, value_type c, const allocator_type& a)
     {
         if (len <= maxSmallString)
         {
             flex_string_details::pod_fill(buf_, buf_ + len, c);
             buf_[maxSmallString] = value_type(maxSmallString - len);
         }
         else
         {
             new(buf_) Storage(len, c, a);
             buf_[maxSmallString] = magic;
         }
     }
 
     SmallStringOpt& operator=(const SmallStringOpt& rhs)
     {
         reserve(rhs.size());
         resize(0, 0);
         append(rhs.data(), rhs.size());
         return *this;
     }
 
     ~SmallStringOpt()
     {
         if (!Small()) GetStorage().~Storage();
     }
 
     iterator begin()
     {
         if (Small()) return buf_;
         return &*GetStorage().begin();
     }
 
     const_iterator begin() const
     {
         if (Small()) return buf_;
         return &*GetStorage().begin();
     }
 
     iterator end()
     {
         if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
         return &*GetStorage().end();
     }
 
     const_iterator end() const
     {
         if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
         return &*GetStorage().end();
     }
 
     size_type size() const
     {
         BOOST_ASSERT(!Small() || maxSmallString >= buf_[maxSmallString]);
         return Small()
             ? maxSmallString - buf_[maxSmallString]
             : GetStorage().size();
     }
 
     size_type max_size() const
     { return boost::allocator_max_size(get_allocator()); }
 
     size_type capacity() const
     { return Small() ? maxSmallString : GetStorage().capacity(); }
 
     void reserve(size_type res_arg)
     {
         if (Small())
         {
             if (res_arg <= maxSmallString) return;
             SmallStringOpt temp(*this);
             this->~SmallStringOpt();
             new(buf_) Storage(temp.data(), temp.size(),
                 temp.get_allocator());
             buf_[maxSmallString] = magic;
             GetStorage().reserve(res_arg);
         }
         else
         {
             GetStorage().reserve(res_arg);
         }
         BOOST_ASSERT(capacity() >= res_arg);
     }
 
     void append(const value_type* s, size_type sz)
     {
         if (!Small())
         {
             GetStorage().append(s, sz);
         }
         else
         {
             // append to a small string
             const size_type neededCapacity =
                 maxSmallString - buf_[maxSmallString] + sz;
 
             if (maxSmallString < neededCapacity)
             {
                 // need to change storage strategy
                 allocator_type alloc;
                 Storage temp(alloc);
                 temp.reserve(neededCapacity);
                 temp.append(buf_, maxSmallString - buf_[maxSmallString]);
                 temp.append(s, sz);
                 buf_[maxSmallString] = magic;
                 new(buf_) Storage(temp.get_allocator());
                 GetStorage().swap(temp);
             }
             else
             {
                 flex_string_details::pod_move(s, s + sz,
                     buf_ + maxSmallString - buf_[maxSmallString]);
                 buf_[maxSmallString] -= value_type(sz);
             }
         }
     }
 
     template <class InputIterator>
     void append(InputIterator b, InputIterator e)
     {
         // @@@ todo: optimize this depending on iterator type
         for (; b != e; ++b)
         {
             *this += *b;
         }
     }
 
     void resize(size_type n, value_type c)
     {
         if (Small())
         {
             if (n > maxSmallString)
             {
                 // Small string resized to big string
                 SmallStringOpt temp(*this); // can't throw
                 // 11-17-2001: correct exception safety bug
                 Storage newString(temp.data(), temp.size(),
                     temp.get_allocator());
                 newString.resize(n, c);
                 // We make the reasonable assumption that an empty Storage
                 //     constructor won't throw
                 this->~SmallStringOpt();
                 new(&buf_[0]) Storage(temp.get_allocator());
                 buf_[maxSmallString] = value_type(magic);
                 GetStorage().swap(newString);
             }
             else
             {
                 // Small string resized to small string
                 // 11-17-2001: bug fix: terminating zero not copied
                 size_type toFill = n > size() ? n - size() : 0;
                 flex_string_details::pod_fill(end(), end() + toFill, c);
                 buf_[maxSmallString] = value_type(maxSmallString - n);
             }
         }
         else
         {
             if (n > maxSmallString)
             {
                 // Big string resized to big string
                 GetStorage().resize(n, c);
             }
             else
             {
                 // Big string resized to small string
                 // 11-17=2001: bug fix in the BOOST_ASSERTion below
                 BOOST_ASSERT(capacity() > n);
                 SmallStringOpt newObj(data(), n, get_allocator());
                 newObj.swap(*this);
             }
         }
     }
 
     void swap(SmallStringOpt& rhs)
     {
         if (Small())
         {
             if (rhs.Small())
             {
                 // Small swapped with small
                 std::swap_ranges(buf_, buf_ + maxSmallString + 1,
                     rhs.buf_);
             }
             else
             {
                 // Small swapped with big
                 // Make a copy of myself - can't throw
                 SmallStringOpt temp(*this);
                 // Nuke myself
                 this->~SmallStringOpt();
                 // Make an empty storage for myself (likely won't throw)
                 new(buf_) Storage(0, value_type(), rhs.get_allocator());
                 buf_[maxSmallString] = magic;
                 // Recurse to this same function
                 swap(rhs);
                 // Nuke rhs
                 rhs.~SmallStringOpt();
                 // Build the new small string into rhs
                 new(&rhs) SmallStringOpt(temp);
             }
         }
         else
         {
             if (rhs.Small())
             {
                 // Big swapped with small
                 // Already implemented, recurse with reversed args
                 rhs.swap(*this);
             }
             else
             {
                 // Big swapped with big
                 GetStorage().swap(rhs.GetStorage());
             }
         }
     }
 
     const value_type* c_str() const
     {
         if (!Small()) return GetStorage().c_str();
         buf_[maxSmallString - buf_[maxSmallString]] = value_type();
         return buf_;
     }
 
     const value_type* data() const
     { return Small() ? buf_ : GetStorage().data(); }
 
     allocator_type get_allocator() const
     { return allocator_type(); }
 };
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template CowString
 // Implements Copy on Write over any storage
 ////////////////////////////////////////////////////////////////////////////////
 
 template <
     typename Storage,
     typename Align = BOOST_DEDUCED_TYPENAME Storage::value_type*
 >
 class CowString
 {
     typedef typename Storage::value_type E;
     typedef typename flex_string_details::get_unsigned<E>::result RefCountType;
 
 public:
     typedef E value_type;
     typedef typename Storage::iterator iterator;
     typedef typename Storage::const_iterator const_iterator;
     typedef typename Storage::allocator_type allocator_type;
     typedef typename boost::allocator_size_type<allocator_type>::type size_type;
     typedef typename Storage::value_type& reference;
 
 private:
     union
     {
         mutable char buf_[sizeof(Storage)];
         Align align_;
     };
 
     Storage& Data() const
     {
         Storage* p = reinterpret_cast<Storage*>(&buf_[0]);
         return *p;
     }
 
     RefCountType GetRefs() const
     {
         const Storage& d = Data();
         BOOST_ASSERT(d.size() > 0);
         BOOST_ASSERT(static_cast<RefCountType>(*d.begin()) != 0);
         return *d.begin();
     }
 
     RefCountType& Refs()
     {
         Storage& d = Data();
         BOOST_ASSERT(d.size() > 0);
         return reinterpret_cast<RefCountType&>(*d.begin());
     }
 
     void MakeUnique() const
     {
         BOOST_ASSERT(GetRefs() >= 1);
         if (GetRefs() == 1) return;
 
         union
         {
             char buf_[sizeof(Storage)];
             Align align_;
         } temp;
 
         --(*Data().begin()); // decrement the use count of the remaining object
 
         Storage* p = reinterpret_cast<Storage*>(&temp.buf_[0]);
         new(buf_) Storage(
             *new(p) Storage(Data()),
             flex_string_details::Shallow());
         *Data().begin() = 1;
     }
 
 public:
     CowString(const CowString& s)
     {
         if (s.GetRefs() == (std::numeric_limits<RefCountType>::max)())
         {
             // must make a brand new copy
             new(buf_) Storage(s.Data()); // non shallow
             Refs() = 1;
         }
         else
         {
             new(buf_) Storage(s.Data(), flex_string_details::Shallow());
             ++Refs();
         }
         BOOST_ASSERT(Data().size() > 0);
     }
 
     CowString(const allocator_type& a)
     {
         new(buf_) Storage(1, 1, a);
     }
 
     CowString(const E* s, size_type len, const allocator_type& a)
     {
         // Warning - MSVC's debugger has trouble tracing through the code below.
         // It seems to be a const-correctness issue
         //
         new(buf_) Storage(a);
         Data().reserve(len + 1);
         Data().resize(1, 1);
         Data().append(s, s + len);
     }
 
     CowString(size_type len, E c, const allocator_type& a)
     {
         new(buf_) Storage(len + 1, c, a);
         Refs() = 1;
     }
 
     CowString& operator=(const CowString& rhs)
     {
 //        CowString(rhs).swap(*this);
         if (--Refs() == 0)
             Data().~Storage();
         if (rhs.GetRefs() == (std::numeric_limits<RefCountType>::max)())
         {
             // must make a brand new copy
             new(buf_) Storage(rhs.Data()); // non shallow
             Refs() = 1;
         }
         else
         {
             new(buf_) Storage(rhs.Data(), flex_string_details::Shallow());
             ++Refs();
         }
         BOOST_ASSERT(Data().size() > 0);
         return *this;
     }
 
     ~CowString()
     {
         BOOST_ASSERT(Data().size() > 0);
         if (--Refs() == 0)
             Data().~Storage();
     }
 
     iterator begin()
     {
         BOOST_ASSERT(Data().size() > 0);
         MakeUnique();
         return Data().begin() + 1;
     }
 
     const_iterator begin() const
     {
         BOOST_ASSERT(Data().size() > 0);
         return Data().begin() + 1;
     }
 
     iterator end()
     {
         MakeUnique();
         return Data().end();
     }
 
     const_iterator end() const
     {
         return Data().end();
     }
 
     size_type size() const
     {
         BOOST_ASSERT(Data().size() > 0);
         return Data().size() - 1;
     }
 
     size_type max_size() const
     {
         BOOST_ASSERT(Data().max_size() > 0);
         return Data().max_size() - 1;
     }
 
     size_type capacity() const
     {
         BOOST_ASSERT(Data().capacity() > 0);
         return Data().capacity() - 1;
     }
 
     void resize(size_type n, E c)
     {
         BOOST_ASSERT(Data().size() > 0);
         MakeUnique();
         Data().resize(n + 1, c);
     }
 
     template <class FwdIterator>
     void append(FwdIterator b, FwdIterator e)
     {
         MakeUnique();
         Data().append(b, e);
     }
 
     void reserve(size_type res_arg)
     {
         if (capacity() > res_arg) return;
         MakeUnique();
         Data().reserve(res_arg + 1);
     }
 
     void swap(CowString& rhs)
     {
         Data().swap(rhs.Data());
     }
 
     const E* c_str() const
     {
         BOOST_ASSERT(Data().size() > 0);
         return Data().c_str() + 1;
     }
 
     const E* data() const
     {
         BOOST_ASSERT(Data().size() > 0);
         return Data().data() + 1;
     }
 
     allocator_type get_allocator() const
     {
         return Data().get_allocator();
     }
 };
 
 ////////////////////////////////////////////////////////////////////////////////
 // class template flex_string
 // a std::basic_string compatible implementation
 // Uses a Storage policy
 ////////////////////////////////////////////////////////////////////////////////
 
 template <typename E,
     class T = std::char_traits<E>,
     class A = std::allocator<E>,
     class Storage = AllocatorStringStorage<E, A> >
 class flex_string : private Storage
 {
 #if defined(BOOST_WAVE_FLEXSTRING_THROW_ON_ENFORCE)
     template <typename Exception>
     static void Enforce(bool condition, Exception*, const char* msg)
     { if (!condition) boost::throw_exception(Exception(msg)); }
 #else
     template <typename Exception>
     static inline void Enforce(bool condition, Exception*, const char* msg)
     { BOOST_ASSERT(condition && msg); }
 #endif // defined(BOOST_WAVE_FLEXSTRING_THROW_ON_ENFORCE)
 
 #ifndef NDEBUG
     bool Sane() const
     {
         return
             begin() <= end() &&
             empty() == (size() == 0) &&
             empty() == (begin() == end()) &&
             size() <= max_size() &&
             capacity() <= max_size() &&
             size() <= capacity();
     }
 
     struct Invariant;
     friend struct Invariant;
     struct Invariant
     {
         Invariant(const flex_string& s) : s_(s)
         {
             BOOST_ASSERT(s_.Sane());
         }
         ~Invariant()
         {
             BOOST_ASSERT(s_.Sane());
         }
     private:
         const flex_string& s_;
         Invariant& operator=(const Invariant&);
     };
 #endif
 
 public:
     // types
     typedef T traits_type;
     typedef typename traits_type::char_type value_type;
     typedef A allocator_type;
 
     typedef typename boost::allocator_value_type<A>::type& reference;
     typedef typename boost::allocator_value_type<A>::type const& const_reference;
     typedef typename boost::allocator_pointer<A>::type pointer;
     typedef typename boost::allocator_const_pointer<A>::type const_pointer;
     typedef typename boost::allocator_size_type<A>::type size_type;
 
     typedef typename Storage::iterator iterator;
     typedef typename Storage::const_iterator const_iterator;
 
     typedef boost::reverse_iterator<iterator> reverse_iterator;
     typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
 
     static const size_type npos;    // = size_type(-1)
 
 private:
     static size_type Min(size_type lhs, size_type rhs)
     { return lhs < rhs ? lhs : rhs; }
     static void Procust(size_type& n, size_type nmax)
     { if (n > nmax) n = nmax; }
 
 public:
     // 21.3.1 construct/copy/destroy
     explicit flex_string(const A& a = A())
     : Storage(a)
     {}
 
     flex_string(const flex_string& str)
     : Storage(str)
     {
     }
 
     flex_string(const flex_string& str, size_type pos,
         size_type n = npos, const A& a = A())
     : Storage(a)
     {
         Enforce(pos <= str.size(), (std::out_of_range*)0, "");
         assign(str, pos, n);
     }
 
     flex_string(const value_type* s, const A& a = A())
     : Storage(s, traits_type::length(s), a)
     {}
 
     flex_string(const value_type* s, size_type n, const A& a = A())
     : Storage(s, n, a)
     {}
 
     flex_string(size_type n, value_type c, const A& a = A())
     : Storage(n, c, a)
     {}
 
     template <class InputIterator>
     flex_string(InputIterator begin, InputIterator end, const A& a = A())
     : Storage(a)
     {
         assign(begin, end);
     }
 
     ~flex_string()
     {}
 
     flex_string& operator=(const flex_string& str)
     {
         if (this != &str) {
             Storage& s = *this;
             s = str;
         }
         return *this;
     }
 
     flex_string& operator=(const value_type* s)
     {
         assign(s);
         return *this;
     }
 
     flex_string& operator=(value_type c)
     {
         assign(1, c);
         return *this;
     }
 
     // 21.3.2 iterators:
     iterator begin()
     { return Storage::begin(); }
 
     const_iterator begin() const
     { return Storage::begin(); }
 
     iterator end()
     { return Storage::end(); }
 
     const_iterator end() const
     { return Storage::end(); }
 
     reverse_iterator rbegin()
     { return reverse_iterator(end()); }
 
     const_reverse_iterator rbegin() const
     { return const_reverse_iterator(end()); }
 
     reverse_iterator rend()
     { return reverse_iterator(begin()); }
 
     const_reverse_iterator rend() const
     { return const_reverse_iterator(begin()); }
 
 #if BOOST_WAVE_FLEX_STRING_SERIALIZATION_HACK != 0
     //  temporary hack to make it easier to serialize flex_string's using
     //  the Boost.Serialization library
     value_type & back() { return *(begin()+size()-1); }
     value_type const& back() const { return *(begin()+size()-1); }
 #endif
 
     // 21.3.3 capacity:
     size_type size() const
     { return Storage::size(); }
 
     size_type length() const
     { return size(); }
 
     size_type max_size() const
     { return Storage::max_size(); }
 
     void resize(size_type n, value_type c)
     { Storage::resize(n, c); }
 
     void resize(size_type n)
     { resize(n, value_type()); }
 
     size_type capacity() const
     { return Storage::capacity(); }
 
     void reserve(size_type res_arg = 0)
     {
         Enforce(res_arg <= max_size(), (std::length_error*)0, "");
         Storage::reserve(res_arg);
     }
 
     void clear()
     { resize(0); }
 
     bool empty() const
     { return size() == 0; }
 
     // 21.3.4 element access:
     const_reference operator[](size_type pos) const
     { return *(begin() + pos); }
 
     reference operator[](size_type pos)
     { return *(begin() + pos); }
 
     const_reference at(size_type n) const
     {
         Enforce(n < size(), (std::out_of_range*)0, "");
         return (*this)[n];
     }
 
     reference at(size_type n)
     {
         Enforce(n < size(), (std::out_of_range*)0, "");
         return (*this)[n];
     }
 
     // 21.3.5 modifiers:
     flex_string& operator+=(const flex_string& str)
     { return append(str); }
 
     flex_string& operator+=(const value_type* s)
     { return append(s); }
 
     flex_string& operator+=(value_type c)
     {
         push_back(c);
         return *this;
     }
 
     flex_string& append(const flex_string& str)
     { return append(str, 0, npos); }
 
     flex_string& append(const flex_string& str, const size_type pos,
         size_type n)
     {
         const size_type sz = str.size();
         Enforce(pos <= sz, (std::out_of_range*)0, "");
         Procust(n, sz - pos);
         return append(str.c_str() + pos, n);
     }
 
     flex_string& append(const value_type* s, const size_type n)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         if (IsAliasedRange(s, s + n))
         {
             const size_type offset = s - &*begin();
             Storage::reserve(size() + n);
             s = &*begin() + offset;
         }
         Storage::append(s, s+ n);
         return *this;
     }
 
     flex_string& append(const value_type* s)
     { return append(s, traits_type::length(s)); }
 
     flex_string& append(size_type n, value_type c)
     {
         resize(size() + n, c);
         return *this;
     }
 
     template<class InputIterator>
     flex_string& append(InputIterator first, InputIterator last)
     {
         insert(end(), first, last);
         return *this;
     }
 
     void push_back(value_type c)
     {
         const size_type cap = capacity();
         if (size() == cap)
         {
             reserve(cap << 1u);
         }
         Storage::append(&c, &c + 1);
     }
 
     flex_string& assign(const flex_string& str)
     {
         if (&str == this) return *this;
         return assign(str.data(), str.size());
     }
 
     flex_string& assign(const flex_string& str, size_type pos,
         size_type n)
     {
         const size_type sz = str.size();
         Enforce(pos <= str.size(), (std::out_of_range*)0, "");
         Procust(n, sz - pos);
         return assign(str.data() + pos, n);
     }
 
     flex_string& assign(const value_type* s, size_type n)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         if (size() >= n)
         {
             std::copy(s, s + n, begin());
             resize(n);
         }
         else
         {
             const value_type *const s2 = s + size();
             std::copy(s, s2, begin());
             append(s2, n - size());
         }
         return *this;
     }
 
     flex_string& assign(const value_type* s)
     { return assign(s, traits_type::length(s)); }
 
     template <class ItOrLength, class ItOrChar>
     flex_string& assign(ItOrLength first_or_n, ItOrChar last_or_c)
     { return replace(begin(), end(), first_or_n, last_or_c); }
 
     flex_string& insert(size_type pos1, const flex_string& str)
     { return insert(pos1, str.data(), str.size()); }
 
     flex_string& insert(size_type pos1, const flex_string& str,
         size_type pos2, size_type n)
     {
         Enforce(pos2 <= str.length(), (std::out_of_range*)0, "");
         Procust(n, str.length() - pos2);
         return insert(pos1, str.data() + pos2, n);
     }
 
     flex_string& insert(size_type pos, const value_type* s, size_type n)
     {
         Enforce(pos <= length(), (std::out_of_range*)0, "");
         insert(begin() + pos, s, s + n);
         return *this;
     }
 
     flex_string& insert(size_type pos, const value_type* s)
     { return insert(pos, s, traits_type::length(s)); }
 
     flex_string& insert(size_type pos, size_type n, value_type c)
     {
         Enforce(pos <= length(), (std::out_of_range*)0, "");
         insert(begin() + pos, n, c);
         return *this;
     }
 
     iterator insert(iterator p, value_type c = value_type())
     {
         const size_type pos = p - begin();
         insert(pos, &c, 1);
         return begin() + pos;
     }
 
 private:
     // Care must be taken when dereferencing some iterator types.
     //
     // Users can implement this function in their namespace if their storage
     // uses a special iterator type, the function will be found through ADL.
     template<class Iterator>
     const typename std::iterator_traits<Iterator>::value_type*
     DereferenceValidIterator(Iterator it) const
     {
         return &*it;
     }
 
     // Care must be taken when dereferencing a reverse iterators, hence this
     // special case. This isn't in the std namespace so as not to pollute it or
     // create name clashes.
     template<typename Iterator>
     const typename std::iterator_traits<Iterator>::value_type*
     DereferenceValidIterator(std::reverse_iterator<Iterator> it) const
     {
         return &*--it;
     }
 
     // Determine if the range aliases the current string.
     //
     // This method cannot be const because calling begin/end on copy-on-write
     // implementations must have side effects.
     // A const version wouldn't make the string unique through this call.
     template<class Iterator>
     bool IsAliasedRange(Iterator beginIterator, Iterator endIterator)
     {
         if(!empty() && beginIterator != endIterator)
         {
             typedef const typename std::iterator_traits<Iterator>::value_type *
                 value_pointer;
 
             value_pointer myBegin(&*begin());
             value_pointer myEnd(&*begin() + size());
             value_pointer rangeBegin(DereferenceValidIterator(beginIterator));
 
             const std::less_equal<value_pointer> less_equal = std::less_equal<value_pointer>();
             if(less_equal(myBegin, rangeBegin) && less_equal(rangeBegin, myEnd))
                 return true;
         }
         return false;
     }
 
     template <int i> class Selector {};
 
     flex_string& InsertImplDiscr(iterator p,
         size_type n, value_type c, Selector<1>)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         BOOST_ASSERT(begin() <= p && p <= end());
         const size_type insertOffset(p - begin());
         const size_type originalSize(size());
         if(n < originalSize - insertOffset)
         {
             // The new characters fit within the original string.
             // The characters that are pushed back need to be moved because
             // they're aliased.
             // The appended characters will all be overwritten by the move.
             append(n, value_type(0));
             value_type* begin(&*begin());
             flex_string_details::pod_move(begin + insertOffset,
                 begin + originalSize, begin + insertOffset + n);
             std::fill(begin + insertOffset, begin + insertOffset + n, c);
         }
         else
         {
             // The new characters exceed the original string.
             // The characters that are pushed back can simply be copied since
             // they aren't aliased.
             // The appended characters will partly be overwritten by the copy.
             append(n, c);
             value_type* begin(&*begin());
             flex_string_details::pod_copy(begin + insertOffset,
                 begin + originalSize, begin + insertOffset + n);
             std::fill(begin + insertOffset, begin + originalSize, c);
         }
         return *this;
     }
 
     template<class InputIterator>
     flex_string& InsertImplDiscr(iterator i,
         InputIterator b, InputIterator e, Selector<0>)
     {
         InsertImpl(i, b, e,
             typename std::iterator_traits<InputIterator>::iterator_category());
         return *this;
     }
 
     template <class FwdIterator>
     void InsertImpl(iterator i,
         FwdIterator s1, FwdIterator s2, std::forward_iterator_tag)
     {
         if(s1 == s2)
         {
             // Insert an empty range.
             return;
         }
 
         if(IsAliasedRange(s1, s2))
         {
             // The source range is contained in the current string, copy it
             // and recurse.
             const flex_string temporary(s1, s2);
             InsertImpl(i, temporary.begin(), temporary.end(),
                 typename std::iterator_traits<FwdIterator>::iterator_category());
             return;
         }
 
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         const size_type pos = i - begin();
         const typename std::iterator_traits<FwdIterator>::difference_type n2 =
             std::distance(s1, s2);
 
         BOOST_ASSERT(n2 >= 0);
         using namespace flex_string_details;
         BOOST_ASSERT(pos <= size());
 
         const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
             capacity() - size();
         if (maxn2 < n2)
         {
             // Reallocate the string.
             BOOST_ASSERT(!IsAliasedRange(s1, s2));
             reserve(size() + n2);
             i = begin() + pos;
         }
         if (pos + n2 <= size())
         {
             const iterator tailBegin = end() - n2;
             Storage::append(tailBegin, tailBegin + n2);
             std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
                 reverse_iterator(tailBegin + n2));
             std::copy(s1, s2, i);
         }
         else
         {
             FwdIterator t = s1;
             const size_type old_size = size();
             std::advance(t, old_size - pos);
             BOOST_ASSERT(std::distance(t, s2) >= 0);
             Storage::append(t, s2);
             Storage::append(data() + pos, data() + old_size);
             std::copy(s1, t, i);
         }
     }
 
     template <class InputIterator>
     void InsertImpl(iterator insertPosition,
         InputIterator inputBegin, InputIterator inputEnd,
         std::input_iterator_tag)
     {
         flex_string temporary(begin(), insertPosition);
         for (; inputBegin != inputEnd; ++inputBegin)
         {
             temporary.push_back(*inputBegin);
         }
         temporary.append(insertPosition, end());
         swap(temporary);
     }
 
 public:
     template <class ItOrLength, class ItOrChar>
     void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c)
     {
         Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
         InsertImplDiscr(p, first_or_n, last_or_c, sel);
     }
 
     flex_string& erase(size_type pos = 0, size_type n = npos)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         Enforce(pos <= length(), (std::out_of_range*)0, "");
         Procust(n, length() - pos);
         std::copy(begin() + pos + n, end(), begin() + pos);
         resize(length() - n);
         return *this;
     }
 
     iterator erase(iterator position)
     {
         const size_type pos(position - begin());
         erase(pos, 1);
         return begin() + pos;
     }
 
     iterator erase(iterator first, iterator last)
     {
         const size_type pos(first - begin());
         erase(pos, last - first);
         return begin() + pos;
     }
 
     // Replaces at most n1 chars of *this, starting with pos1 with the content of str
     flex_string& replace(size_type pos1, size_type n1, const flex_string& str)
     { return replace(pos1, n1, str, 0, npos); }
 
     // Replaces at most n1 chars of *this, starting with pos1,
     // with at most n2 chars of str starting with pos2
     flex_string& replace(size_type pos1, size_type n1, const flex_string& str,
         size_type pos2, size_type n2)
     {
         Enforce(pos2 <= str.length(), (std::out_of_range*)0, "");
         return replace(pos1, n1, str.data() + pos2,
             Min(n2, str.size() - pos2));
     }
 
     // Replaces at most n1 chars of *this, starting with pos, with chars from s
     flex_string& replace(size_type pos, size_type n1, const value_type* s)
     { return replace(pos, n1, s, traits_type::length(s)); }
 
     // Replaces at most n1 chars of *this, starting with pos, with n2 occurrences of c
     // consolidated with
     // Replaces at most n1 chars of *this, starting with pos,
     // with at most n2 chars of str.
     // str must have at least n2 chars.
     template <class StrOrLength, class NumOrChar>
     flex_string& replace(size_type pos, size_type n1,
         StrOrLength s_or_n2, NumOrChar n_or_c)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         Enforce(pos <= size(), (std::out_of_range*)0, "");
         Procust(n1, length() - pos);
         const iterator b = begin() + pos;
         return replace(b, b + n1, s_or_n2, n_or_c);
     }
 
     flex_string& replace(iterator i1, iterator i2, const flex_string& str)
     { return replace(i1, i2, str.c_str(), str.length()); }
 
     flex_string& replace(iterator i1, iterator i2, const value_type* s)
     { return replace(i1, i2, s, traits_type::length(s)); }
 
 private:
     flex_string& ReplaceImplDiscr(iterator i1, iterator i2,
         const value_type* s, size_type n, Selector<2>)
     {
         BOOST_ASSERT(i1 <= i2);
         BOOST_ASSERT(begin() <= i1 && i1 <= end());
         BOOST_ASSERT(begin() <= i2 && i2 <= end());
         return replace(i1, i2, s, s + n);
     }
 
     flex_string& ReplaceImplDiscr(iterator i1, iterator i2,
         size_type n2, value_type c, Selector<1>)
     {
         const size_type n1 = i2 - i1;
         if (n1 > n2)
         {
             std::fill(i1, i1 + n2, c);
             erase(i1 + n2, i2);
         }
         else
         {
             std::fill(i1, i2, c);
             insert(i2, n2 - n1, c);
         }
         return *this;
     }
 
     template <class InputIterator>
     flex_string& ReplaceImplDiscr(iterator i1, iterator i2,
         InputIterator b, InputIterator e, Selector<0>)
     {
         ReplaceImpl(i1, i2, b, e,
             typename std::iterator_traits<InputIterator>::iterator_category());
         return *this;
     }
 
     template <class FwdIterator>
     void ReplaceImpl(iterator i1, iterator i2,
         FwdIterator s1, FwdIterator s2, std::forward_iterator_tag)
     {
 #ifndef NDEBUG
         Invariant checker(*this);
 #endif
         const typename std::iterator_traits<iterator>::difference_type n1 =
             i2 - i1;
         BOOST_ASSERT(n1 >= 0);
         const typename std::iterator_traits<FwdIterator>::difference_type n2 =
             std::distance(s1, s2);
         BOOST_ASSERT(n2 >= 0);
 
         if (IsAliasedRange(s1, s2))
         {
             // Aliased replace, copy to new string.
             flex_string temporary;
             temporary.reserve(size() - n1 + n2);
             temporary.append(begin(), i1).append(s1, s2).append(i2, end());
             swap(temporary);
             return;
         }
 
         if (n1 > n2)
         {
             // Shrinks
             std::copy(s1, s2, i1);
             erase(i1 + n2, i2);
         }
         else
         {
             // Grows
             flex_string_details::copy_n(s1, n1, i1);
             std::advance(s1, n1);
             insert(i2, s1, s2);
         }
     }
 
     template <class InputIterator>
     void ReplaceImpl(iterator i1, iterator i2,
         InputIterator b, InputIterator e, std::input_iterator_tag)
     {
         flex_string temp(begin(), i1);
         temp.append(b, e).append(i2, end());
         swap(temp);
     }
 
 public:
     template <class T1, class T2>
     flex_string& replace(iterator i1, iterator i2,
         T1 first_or_n_or_s, T2 last_or_c_or_n)
     {
         const bool
             num1 = std::numeric_limits<T1>::is_specialized,
             num2 = std::numeric_limits<T2>::is_specialized;
         return ReplaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n,
             Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
     }
 
     size_type copy(value_type* s, size_type n, size_type pos = 0) const
     {
         Enforce(pos <= size(), (std::out_of_range*)0, "");
         n = Min(n, size() - pos);
 
         flex_string_details::pod_copy(
             &*begin() + pos,
             &*begin() + pos + n,
             s);
         return n;
     }
 
     void swap(flex_string& rhs)
     {
         Storage& srhs = rhs;
         this->Storage::swap(srhs);
     }
 
     // 21.3.6 string operations:
     const value_type* c_str() const
     { return Storage::c_str(); }
 
     const value_type* data() const
     { return Storage::data(); }
 
     allocator_type get_allocator() const
     { return Storage::get_allocator(); }
 
     size_type find(const flex_string& str, size_type pos = 0) const
     { return find(str.data(), pos, str.length()); }
 
     size_type find (const value_type* s, size_type pos, size_type n) const
     {
         const size_type size_(size());
         if (n + pos > size_)
             return npos;
         for (; pos < size_; ++pos)
         {
             if (traits_type::compare(&*begin() + pos, s, n) == 0)
             {
                 return pos;
             }
         }
         return npos;
     }
 
     size_type find (const value_type* s, size_type pos = 0) const
     { return find(s, pos, traits_type::length(s)); }
 
     size_type find (value_type c, size_type pos = 0) const
     { return find(&c, pos, 1); }
 
     size_type rfind(const flex_string& str, size_type pos = npos) const
     { return rfind(str.c_str(), pos, str.length()); }
 
     size_type rfind(const value_type* s, size_type pos, size_type n) const
     {
         if (n > length()) return npos;
         pos = Min(pos, length() - n);
         if (n == 0) return pos;
 
         const_iterator i(begin() + pos);
         for (; ; --i)
         {
             if (traits_type::eq(*i, *s)
                 && traits_type::compare(&*i, s, n) == 0)
             {
                 return i - begin();
             }
             if (i == begin()) break;
         }
         return npos;
     }
 
     size_type rfind(const value_type* s, size_type pos = npos) const
     { return rfind(s, pos, traits_type::length(s)); }
 
     size_type rfind(value_type c, size_type pos = npos) const
     { return rfind(&c, pos, 1); }
 
     size_type find_first_of(const flex_string& str, size_type pos = 0) const
     { return find_first_of(str.c_str(), pos, str.length()); }
 
     size_type find_first_of(const value_type* s,
         size_type pos, size_type n) const
     {
         if (pos > length() || n == 0) return npos;
         const_iterator i(begin() + pos),
             finish(end());
         for (; i != finish; ++i)
         {
             if (traits_type::find(s, n, *i) != 0)
             {
                 return i - begin();
             }
         }
         return npos;
     }
 
     size_type find_first_of(const value_type* s, size_type pos = 0) const
     { return find_first_of(s, pos, traits_type::length(s)); }
 
     size_type find_first_of(value_type c, size_type pos = 0) const
     { return find_first_of(&c, pos, 1); }
 
     size_type find_last_of (const flex_string& str,
         size_type pos = npos) const
     { return find_last_of(str.c_str(), pos, str.length()); }
 
     size_type find_last_of (const value_type* s, size_type pos,
         size_type n) const
     {
         if (!empty() && n > 0)
         {
             pos = Min(pos, length() - 1);
             const_iterator i(begin() + pos);
             for (;; --i)
             {
                 if (traits_type::find(s, n, *i) != 0)
                 {
                     return i - begin();
                 }
                 if (i == begin()) break;
             }
         }
         return npos;
     }
 
     size_type find_last_of (const value_type* s,
         size_type pos = npos) const
     { return find_last_of(s, pos, traits_type::length(s)); }
 
     size_type find_last_of (value_type c, size_type pos = npos) const
     { return find_last_of(&c, pos, 1); }
 
     size_type find_first_not_of(const flex_string& str,
         size_type pos = 0) const
     { return find_first_not_of(str.data(), pos, str.size()); }
 
     size_type find_first_not_of(const value_type* s, size_type pos,
         size_type n) const
     {
         if (pos < length())
         {
             const_iterator
                 i(begin() + pos),
                 finish(end());
             for (; i != finish; ++i)
             {
                 if (traits_type::find(s, n, *i) == 0)
                 {
                     return i - begin();
                 }
             }
         }
         return npos;
     }
 
     size_type find_first_not_of(const value_type* s,
         size_type pos = 0) const
     { return find_first_not_of(s, pos, traits_type::length(s)); }
 
     size_type find_first_not_of(value_type c, size_type pos = 0) const
     { return find_first_not_of(&c, pos, 1); }
 
     size_type find_last_not_of(const flex_string& str,
         size_type pos = npos) const
     { return find_last_not_of(str.c_str(), pos, str.length()); }
 
     size_type find_last_not_of(const value_type* s, size_type pos,
         size_type n) const
     {
         if (!empty())
         {
             pos = Min(pos, size() - 1);
             const_iterator i(begin() + pos);
             for (;; --i)
             {
                 if (traits_type::find(s, n, *i) == 0)
                 {
                     return i - begin();
                 }
                 if (i == begin()) break;
             }
         }
         return npos;
     }
 
     size_type find_last_not_of(const value_type* s,
         size_type pos = npos) const
     { return find_last_not_of(s, pos, traits_type::length(s)); }
 
     size_type find_last_not_of (value_type c, size_type pos = npos) const
     { return find_last_not_of(&c, pos, 1); }
 
     flex_string substr(size_type pos = 0, size_type n = npos) const
     {
         Enforce(pos <= size(), (std::out_of_range*)0, "");
         return flex_string(data() + pos, Min(n, size() - pos));
     }
 
     std::ptrdiff_t compare(const flex_string& str) const
     {
         // FIX due to Goncalo N M de Carvalho July 18, 2005
         return compare(0, size(), str);
     }
 
     std::ptrdiff_t compare(size_type pos1, size_type n1,
         const flex_string& str) const
     { return compare(pos1, n1, str.data(), str.size()); }
 
     // FIX to compare: added the TC
     // (http://www.comeaucomputing.com/iso/lwg-defects.html number 5)
     // Thanks to Caleb Epstein for the fix
     std::ptrdiff_t compare(size_type pos1, size_type n1,
         const value_type* s) const
     {
         return compare(pos1, n1, s, traits_type::length(s));
     }
 
     std::ptrdiff_t compare(size_type pos1, size_type n1,
         const value_type* s, size_type n2) const
     {
         Enforce(pos1 <= size(), (std::out_of_range*)0, "");
         Procust(n1, size() - pos1);
         const int r = traits_type::compare(pos1 + data(), s, Min(n1, n2));
         return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
     }
 
     std::ptrdiff_t compare(size_type pos1, size_type n1,
         const flex_string& str,
         size_type pos2, size_type n2) const
     {
         Enforce(pos2 <= str.size(), (std::out_of_range*)0, "");
         return compare(pos1, n1, str.data() + pos2, Min(n2, str.size() - pos2));
     }
 
     std::ptrdiff_t compare(const value_type* s) const
     {
         // Could forward to compare(0, size(), s, traits_type::length(s))
         // but that does two extra checks
         const size_type n1(size()), n2(traits_type::length(s));
         const int r = traits_type::compare(data(), s, Min(n1, n2));
         return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
     }
 };
 
 // non-member functions
 template <typename E, class T, class A, class S>
 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 {
     flex_string<E, T, A, S> result;
     result.reserve(lhs.size() + rhs.size());
     result.append(lhs).append(rhs);
     return result;
 }
 
 template <typename E, class T, class A, class S>
 flex_string<E, T, A, S> operator+(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 {
     flex_string<E, T, A, S> result;
     const typename flex_string<E, T, A, S>::size_type len =
         flex_string<E, T, A, S>::traits_type::length(lhs);
     result.reserve(len + rhs.size());
     result.append(lhs, len).append(rhs);
     return result;
 }
 
 template <typename E, class T, class A, class S>
 flex_string<E, T, A, S> operator+(
     typename flex_string<E, T, A, S>::value_type lhs,
     const flex_string<E, T, A, S>& rhs)
 {
     flex_string<E, T, A, S> result;
     result.reserve(1 + rhs.size());
     result.push_back(lhs);
     result.append(rhs);
     return result;
 }
 
 template <typename E, class T, class A, class S>
 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 {
     typedef typename flex_string<E, T, A, S>::size_type size_type;
     typedef typename flex_string<E, T, A, S>::traits_type traits_type;
 
     flex_string<E, T, A, S> result;
     const size_type len = traits_type::length(rhs);
     result.reserve(lhs.size() + len);
     result.append(lhs).append(rhs, len);
     return result;
 }
 
 template <typename E, class T, class A, class S>
 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
     typename flex_string<E, T, A, S>::value_type rhs)
 {
     flex_string<E, T, A, S> result;
     result.reserve(lhs.size() + 1);
     result.append(lhs);
     result.push_back(rhs);
     return result;
 }
 
 template <typename E, class T, class A, class S>
 inline bool operator==(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return lhs.compare(rhs) == 0; }
 
 template <typename E, class T, class A, class S>
 inline bool operator==(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return rhs == lhs; }
 
 template <typename E, class T, class A, class S>
 inline bool operator==(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return lhs.compare(rhs) == 0; }
 
 template <typename E, class T, class A, class S>
 inline bool operator!=(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(lhs == rhs); }
 
 template <typename E, class T, class A, class S>
 inline bool operator!=(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(lhs == rhs); }
 
 template <typename E, class T, class A, class S>
 inline bool operator!=(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return !(lhs == rhs); }
 
 template <typename E, class T, class A, class S>
 inline bool operator<(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return lhs.compare(rhs) < 0; }
 
 template <typename E, class T, class A, class S>
 inline bool operator<(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return lhs.compare(rhs) < 0; }
 
 template <typename E, class T, class A, class S>
 inline bool operator<(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return rhs.compare(lhs) > 0; }
 
 template <typename E, class T, class A, class S>
 inline bool operator>(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return rhs < lhs; }
 
 template <typename E, class T, class A, class S>
 inline bool operator>(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return rhs < lhs; }
 
 template <typename E, class T, class A, class S>
 bool operator>(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return rhs < lhs; }
 
 template <typename E, class T, class A, class S>
 inline bool operator<=(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(rhs < lhs); }
 
 template <typename E, class T, class A, class S>
 inline bool operator<=(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return !(rhs < lhs); }
 
 template <typename E, class T, class A, class S>
 bool operator<=(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(rhs < lhs); }
 
 template <typename E, class T, class A, class S>
 bool operator>=(const flex_string<E, T, A, S>& lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(lhs < rhs); }
 
 template <typename E, class T, class A, class S>
 bool operator>=(const flex_string<E, T, A, S>& lhs,
     const typename flex_string<E, T, A, S>::value_type* rhs)
 { return !(lhs < rhs); }
 
 template <typename E, class T, class A, class S>
 inline bool operator>=(const typename flex_string<E, T, A, S>::value_type* lhs,
     const flex_string<E, T, A, S>& rhs)
 { return !(lhs < rhs); }
 
 template <typename E, class T, class A, class S>
 void swap(flex_string<E, T, A, S>& lhs, flex_string<E, T, A, S>& rhs)
 {
     // subclause 21.3.7.8:
     lhs.swap(rhs);
 }
 
 template <typename E, class T, class A, class S>
 inline std::basic_istream<typename flex_string<E, T, A, S>::value_type,
     typename flex_string<E, T, A, S>::traits_type>&
 operator>>(
     std::basic_istream<typename flex_string<E, T, A, S>::value_type,
     typename flex_string<E, T, A, S>::traits_type>& is,
     flex_string<E, T, A, S>& str);
 
 template <typename E, class T, class A, class S>
 std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
     typename flex_string<E, T, A, S>::traits_type>&
 operator<<(
     std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
     typename flex_string<E, T, A, S>::traits_type>& os,
     const flex_string<E, T, A, S>& str)
 { return os << str.c_str(); }
 
 template <typename E1, class T, class A, class S>
 const typename flex_string<E1, T, A, S>::size_type
 flex_string<E1, T, A, S>::npos = (typename flex_string<E1, T, A, S>::size_type)(-1);
 
 ///////////////////////////////////////////////////////////////////////////////
 }   // namespace util
 }   // namespace wave
 }   // namespace boost
 
 #if BOOST_WAVE_SERIALIZATION != 0
 ///////////////////////////////////////////////////////////////////////////////
 namespace boost { namespace serialization {
 
 #if !defined(BOOST_WAVE_FLEX_STRING_SERIALIZATION_HACK)
 
 // FIXME: This doesn't work because of the missing flex_string::operator>>()
 template <typename E, class T, class A, class S>
 struct implementation_level<boost::wave::util::flex_string<E, T, A, S> >
 {
     typedef mpl::integral_c_tag tag;
     typedef mpl::int_<boost::serialization::primitive_type> type;
     BOOST_STATIC_CONSTANT(
         int,
         value = implementation_level::type::value
     );
 };
 
 #else
 
 //  We serialize flex_strings as vectors of char's for now
 template<class Archive, typename E, class T, class A, class S>
 inline void save(Archive & ar,
     boost::wave::util::flex_string<E, T, A, S> const &t,
     const unsigned int file_version)
 {
     boost::serialization::stl::save_collection<
         Archive, wave::util::flex_string<E, T, A, S> >(ar, t);
 }
 
 template<class Archive, typename E, class T, class A, class S>
 inline void load(Archive & ar, boost::wave::util::flex_string<E, T, A, S> &t,
     const unsigned int file_version)
 {
     boost::serialization::stl::load_collection<
         Archive, boost::wave::util::flex_string<E, T, A, S>,
         boost::serialization::stl::archive_input_seq<
             Archive, boost::wave::util::flex_string<E, T, A, S> >,
         boost::serialization::stl::reserve_imp<
             boost::wave::util::flex_string<E, T, A, S> >
     >(ar, t);
 }
 
 // split non-intrusive serialization function member into separate
 // non intrusive save/load member functions
 template<class Archive, typename E, class T, class A, class S>
 inline void serialize(Archive & ar, boost::wave::util::flex_string<E, T, A, S> &t,
     const unsigned int file_version)
 {
     boost::serialization::split_free(ar, t, file_version);
 }
 
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
 }} // boost::serialization
 #endif
 
 // the suffix header occurs after all of the code
 #ifdef BOOST_HAS_ABI_HEADERS
 #include BOOST_ABI_SUFFIX
 #endif
 
 #endif // BOOST_FLEX_STRING_INC_