diff options
Diffstat (limited to 'libstdc++-v3/include/bits')
41 files changed, 5972 insertions, 211 deletions
diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc index d450a4717de..ab71ad67e17 100644 --- a/libstdc++-v3/include/bits/basic_string.tcc +++ b/libstdc++-v3/include/bits/basic_string.tcc @@ -1,7 +1,7 @@ // Components for manipulating sequences of characters -*- C++ -*- // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, -// 2006, 2007, 2008, 2009 +// 2006, 2007, 2008, 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -130,7 +130,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) #endif // NB: Not required, but considered best practice. if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) - __throw_logic_error(__N("basic_string::_S_construct NULL not valid")); + __throw_logic_error(__N("basic_string::_S_construct null not valid")); const size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); diff --git a/libstdc++-v3/include/bits/boost_concept_check.h b/libstdc++-v3/include/bits/boost_concept_check.h index 054fcf27e5e..cffd7fb2d05 100644 --- a/libstdc++-v3/include/bits/boost_concept_check.h +++ b/libstdc++-v3/include/bits/boost_concept_check.h @@ -1,6 +1,7 @@ // -*- C++ -*- -// Copyright (C) 2004, 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// Copyright (C) 2004, 2005, 2006, 2007, 2009, 2010 +// Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -41,7 +42,7 @@ #pragma GCC system_header -#include <cstddef> // for ptrdiff_t, used next +#include <bits/c++config.h> #include <bits/stl_iterator_base_types.h> // for traits and tags _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config index 3746696458a..9dc9ac24cd8 100644 --- a/libstdc++-v3/include/bits/c++config +++ b/libstdc++-v3/include/bits/c++config @@ -1,7 +1,7 @@ // Predefined symbols and macros -*- C++ -*- // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, -// 2006, 2007, 2008, 2009 Free Software Foundation, Inc. +// 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -376,4 +376,19 @@ _GLIBCXX_END_NAMESPACE # endif #endif +#ifdef __cplusplus + +_GLIBCXX_BEGIN_NAMESPACE(std) + + typedef __SIZE_TYPE__ size_t; + typedef __PTRDIFF_TYPE__ ptrdiff_t; + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + typedef decltype(nullptr) nullptr_t; +#endif + +_GLIBCXX_END_NAMESPACE + +#endif // __cplusplus + // End of prewritten config; the discovered settings follow. diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index cde067cf382..d8c27870647 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -1,6 +1,7 @@ // Deque implementation (out of line) -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, +// 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -59,6 +60,33 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template <typename _Tp, typename _Alloc> + void + deque<_Tp, _Alloc>:: + _M_default_initialize() + { + _Map_pointer __cur; + __try + { + for (__cur = this->_M_impl._M_start._M_node; + __cur < this->_M_impl._M_finish._M_node; + ++__cur) + std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), + _M_get_Tp_allocator()); + std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, + this->_M_impl._M_finish._M_cur, + _M_get_Tp_allocator()); + } + __catch(...) + { + std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), + _M_get_Tp_allocator()); + __throw_exception_again; + } + } +#endif + template <typename _Tp, typename _Alloc> deque<_Tp, _Alloc>& deque<_Tp, _Alloc>:: @@ -271,6 +299,32 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) _M_insert_aux(__pos, __n, __x); } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template <typename _Tp, typename _Alloc> + void + deque<_Tp, _Alloc>:: + _M_default_append(size_type __n) + { + if (__n) + { + iterator __new_finish = _M_reserve_elements_at_back(__n); + __try + { + std::__uninitialized_default_a(this->_M_impl._M_finish, + __new_finish, + _M_get_Tp_allocator()); + this->_M_impl._M_finish = __new_finish; + } + __catch(...) + { + _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, + __new_finish._M_node + 1); + __throw_exception_again; + } + } + } +#endif + template <typename _Tp, typename _Alloc> void deque<_Tp, _Alloc>:: diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h index c0c135cd1b3..3708a62c37d 100644 --- a/libstdc++-v3/include/bits/forward_list.h +++ b/libstdc++-v3/include/bits/forward_list.h @@ -463,7 +463,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * constructed elements. */ explicit - forward_list(size_type __n); + forward_list(size_type __n) + : _Base() + { _M_default_initialize(__n); } /** * @brief Creates a %forward_list with copies of an exemplar element. @@ -1209,6 +1211,14 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // Called by splice_after and insert_after. iterator _M_splice_after(const_iterator __pos, forward_list&& __list); + + // Called by forward_list(n). + void + _M_default_initialize(size_type __n); + + // Called by resize(sz). + void + _M_default_insert_after(const_iterator __pos, size_type __n); }; /** diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index 7468a90d1af..a3719a8698d 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -114,7 +114,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _M_fill_initialize(size_type __n, const value_type& __value) { _Node_base* __to = &this->_M_impl._M_head; - for (; __n > 0; --__n) + for (; __n; --__n) { __to->_M_next = this->_M_create_node(__value); __to = __to->_M_next; @@ -122,12 +122,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } template<typename _Tp, typename _Alloc> + void forward_list<_Tp, _Alloc>:: - forward_list(size_type __n) - : _Base() + _M_default_initialize(size_type __n) { _Node_base* __to = &this->_M_impl._M_head; - for (; __n > 0; --__n) + for (; __n; --__n) { __to->_M_next = this->_M_create_node(); __to = __to->_M_next; @@ -164,6 +164,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template<typename _Tp, typename _Alloc> void forward_list<_Tp, _Alloc>:: + _M_default_insert_after(const_iterator __pos, size_type __n) + { + const_iterator __saved_pos = __pos; + __try + { + for (; __n; --__n) + __pos = emplace_after(__pos); + } + __catch(...) + { + erase_after(__saved_pos, ++__pos); + __throw_exception_again; + } + } + + template<typename _Tp, typename _Alloc> + void + forward_list<_Tp, _Alloc>:: resize(size_type __sz) { iterator __k = before_begin(); @@ -177,10 +195,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (__len == __sz) erase_after(__k, end()); else - { - forward_list __tmp(__sz - __len); - splice_after(__k, std::move(__tmp)); - } + _M_default_insert_after(__k, __sz - __len); } template<typename _Tp, typename _Alloc> diff --git a/libstdc++-v3/include/bits/fstream.tcc b/libstdc++-v3/include/bits/fstream.tcc index c5f7f8c52af..c498f48caee 100644 --- a/libstdc++-v3/include/bits/fstream.tcc +++ b/libstdc++-v3/include/bits/fstream.tcc @@ -64,21 +64,21 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (_M_buf_allocated) { delete [] _M_buf; - _M_buf = NULL; + _M_buf = 0; _M_buf_allocated = false; } delete [] _M_ext_buf; - _M_ext_buf = NULL; + _M_ext_buf = 0; _M_ext_buf_size = 0; - _M_ext_next = NULL; - _M_ext_end = NULL; + _M_ext_next = 0; + _M_ext_end = 0; } template<typename _CharT, typename _Traits> basic_filebuf<_CharT, _Traits>:: basic_filebuf() : __streambuf_type(), _M_lock(), _M_file(&_M_lock), _M_mode(ios_base::openmode(0)), _M_state_beg(), _M_state_cur(), - _M_state_last(), _M_buf(NULL), _M_buf_size(BUFSIZ), + _M_state_last(), _M_buf(0), _M_buf_size(BUFSIZ), _M_buf_allocated(false), _M_reading(false), _M_writing(false), _M_pback(), _M_pback_cur_save(0), _M_pback_end_save(0), _M_pback_init(false), _M_codecvt(0), _M_ext_buf(0), _M_ext_buf_size(0), _M_ext_next(0), @@ -93,7 +93,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) basic_filebuf<_CharT, _Traits>:: open(const char* __s, ios_base::openmode __mode) { - __filebuf_type *__ret = NULL; + __filebuf_type *__ret = 0; if (!this->is_open()) { _M_file.open(__s, __mode); @@ -128,7 +128,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) close() { if (!this->is_open()) - return NULL; + return 0; bool __testfail = false; { @@ -167,7 +167,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __testfail = true; if (__testfail) - return NULL; + return 0; else return this; } diff --git a/libstdc++-v3/include/bits/functional_hash.h b/libstdc++-v3/include/bits/functional_hash.h index aaa05aad689..a207ffa6bd0 100644 --- a/libstdc++-v3/include/bits/functional_hash.h +++ b/libstdc++-v3/include/bits/functional_hash.h @@ -32,7 +32,7 @@ #pragma GCC system_header -#include <cstddef> +#include <bits/c++config.h> #include <bits/stl_function.h> namespace std diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index f1c4a10dd66..3446c42a85b 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -112,6 +112,56 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) return __ret; } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<typename _Tp, typename _Alloc> + void + list<_Tp, _Alloc>:: + _M_default_append(size_type __n) + { + size_type __i = 0; + __try + { + for (; __i < __n; ++__i) + emplace_back(); + } + __catch(...) + { + for (; __i; --__i) + pop_back(); + __throw_exception_again; + } + } + + template<typename _Tp, typename _Alloc> + void + list<_Tp, _Alloc>:: + resize(size_type __new_size) + { + iterator __i = begin(); + size_type __len = 0; + for (; __i != end() && __len < __new_size; ++__i, ++__len) + ; + if (__len == __new_size) + erase(__i, end()); + else // __i == end() + _M_default_append(__new_size - __len); + } + + template<typename _Tp, typename _Alloc> + void + list<_Tp, _Alloc>:: + resize(size_type __new_size, const value_type& __x) + { + iterator __i = begin(); + size_type __len = 0; + for (; __i != end() && __len < __new_size; ++__i, ++__len) + ; + if (__len == __new_size) + erase(__i, end()); + else // __i == end() + insert(end(), __new_size - __len, __x); + } +#else template<typename _Tp, typename _Alloc> void list<_Tp, _Alloc>:: @@ -126,6 +176,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) else // __i == end() insert(end(), __new_size - __len, __x); } +#endif template<typename _Tp, typename _Alloc> list<_Tp, _Alloc>& diff --git a/libstdc++-v3/include/bits/locale_facets.h b/libstdc++-v3/include/bits/locale_facets.h index 2e18f7da8ed..79bfd03026d 100644 --- a/libstdc++-v3/include/bits/locale_facets.h +++ b/libstdc++-v3/include/bits/locale_facets.h @@ -1587,12 +1587,13 @@ _GLIBCXX_BEGIN_NAMESPACE(std) bool _M_allocated; - __numpunct_cache(size_t __refs = 0) : facet(__refs), - _M_grouping(NULL), _M_grouping_size(0), _M_use_grouping(false), - _M_truename(NULL), _M_truename_size(0), _M_falsename(NULL), - _M_falsename_size(0), _M_decimal_point(_CharT()), - _M_thousands_sep(_CharT()), _M_allocated(false) - { } + __numpunct_cache(size_t __refs = 0) + : facet(__refs), _M_grouping(0), _M_grouping_size(0), + _M_use_grouping(false), + _M_truename(0), _M_truename_size(0), _M_falsename(0), + _M_falsename_size(0), _M_decimal_point(_CharT()), + _M_thousands_sep(_CharT()), _M_allocated(false) + { } ~__numpunct_cache(); @@ -1657,7 +1658,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param refs Refcount to pass to the base class. */ explicit - numpunct(size_t __refs = 0) : facet(__refs), _M_data(NULL) + numpunct(size_t __refs = 0) + : facet(__refs), _M_data(0) { _M_initialize_numpunct(); } /** @@ -1685,7 +1687,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) */ explicit numpunct(__c_locale __cloc, size_t __refs = 0) - : facet(__refs), _M_data(NULL) + : facet(__refs), _M_data(0) { _M_initialize_numpunct(__cloc); } /** @@ -1841,7 +1843,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // For use at construction time only. void - _M_initialize_numpunct(__c_locale __cloc = NULL); + _M_initialize_numpunct(__c_locale __cloc = 0); }; template<typename _CharT> diff --git a/libstdc++-v3/include/bits/locale_facets.tcc b/libstdc++-v3/include/bits/locale_facets.tcc index 1608e2c42da..52bafd36dfe 100644 --- a/libstdc++-v3/include/bits/locale_facets.tcc +++ b/libstdc++-v3/include/bits/locale_facets.tcc @@ -1,7 +1,7 @@ // Locale support -*- C++ -*- // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, -// 2006, 2007, 2008, 2009 +// 2006, 2007, 2008, 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -56,7 +56,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) const locale::facet** __caches = __loc._M_impl->_M_caches; if (!__caches[__i]) { - __numpunct_cache<_CharT>* __tmp = NULL; + __numpunct_cache<_CharT>* __tmp = 0; __try { __tmp = new __numpunct_cache<_CharT>; diff --git a/libstdc++-v3/include/bits/locale_facets_nonio.h b/libstdc++-v3/include/bits/locale_facets_nonio.h index a25e0acd2c0..fdc810d12be 100644 --- a/libstdc++-v3/include/bits/locale_facets_nonio.h +++ b/libstdc++-v3/include/bits/locale_facets_nonio.h @@ -118,20 +118,20 @@ _GLIBCXX_BEGIN_NAMESPACE(std) bool _M_allocated; __timepunct_cache(size_t __refs = 0) : facet(__refs), - _M_date_format(NULL), _M_date_era_format(NULL), _M_time_format(NULL), - _M_time_era_format(NULL), _M_date_time_format(NULL), - _M_date_time_era_format(NULL), _M_am(NULL), _M_pm(NULL), - _M_am_pm_format(NULL), _M_day1(NULL), _M_day2(NULL), _M_day3(NULL), - _M_day4(NULL), _M_day5(NULL), _M_day6(NULL), _M_day7(NULL), - _M_aday1(NULL), _M_aday2(NULL), _M_aday3(NULL), _M_aday4(NULL), - _M_aday5(NULL), _M_aday6(NULL), _M_aday7(NULL), _M_month01(NULL), - _M_month02(NULL), _M_month03(NULL), _M_month04(NULL), _M_month05(NULL), - _M_month06(NULL), _M_month07(NULL), _M_month08(NULL), _M_month09(NULL), - _M_month10(NULL), _M_month11(NULL), _M_month12(NULL), _M_amonth01(NULL), - _M_amonth02(NULL), _M_amonth03(NULL), _M_amonth04(NULL), - _M_amonth05(NULL), _M_amonth06(NULL), _M_amonth07(NULL), - _M_amonth08(NULL), _M_amonth09(NULL), _M_amonth10(NULL), - _M_amonth11(NULL), _M_amonth12(NULL), _M_allocated(false) + _M_date_format(0), _M_date_era_format(0), _M_time_format(0), + _M_time_era_format(0), _M_date_time_format(0), + _M_date_time_era_format(0), _M_am(0), _M_pm(0), + _M_am_pm_format(0), _M_day1(0), _M_day2(0), _M_day3(0), + _M_day4(0), _M_day5(0), _M_day6(0), _M_day7(0), + _M_aday1(0), _M_aday2(0), _M_aday3(0), _M_aday4(0), + _M_aday5(0), _M_aday6(0), _M_aday7(0), _M_month01(0), + _M_month02(0), _M_month03(0), _M_month04(0), _M_month05(0), + _M_month06(0), _M_month07(0), _M_month08(0), _M_month09(0), + _M_month10(0), _M_month11(0), _M_month12(0), _M_amonth01(0), + _M_amonth02(0), _M_amonth03(0), _M_amonth04(0), + _M_amonth05(0), _M_amonth06(0), _M_amonth07(0), + _M_amonth08(0), _M_amonth09(0), _M_amonth10(0), + _M_amonth11(0), _M_amonth12(0), _M_allocated(false) { } ~__timepunct_cache(); @@ -313,7 +313,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // For use at construction time only. void - _M_initialize_timepunct(__c_locale __cloc = NULL); + _M_initialize_timepunct(__c_locale __cloc = 0); }; template<typename _CharT> @@ -883,11 +883,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) bool _M_allocated; __moneypunct_cache(size_t __refs = 0) : facet(__refs), - _M_grouping(NULL), _M_grouping_size(0), _M_use_grouping(false), + _M_grouping(0), _M_grouping_size(0), _M_use_grouping(false), _M_decimal_point(_CharT()), _M_thousands_sep(_CharT()), - _M_curr_symbol(NULL), _M_curr_symbol_size(0), - _M_positive_sign(NULL), _M_positive_sign_size(0), - _M_negative_sign(NULL), _M_negative_sign_size(0), + _M_curr_symbol(0), _M_curr_symbol_size(0), + _M_positive_sign(0), _M_positive_sign_size(0), + _M_negative_sign(0), _M_negative_sign_size(0), _M_frac_digits(0), _M_pos_format(money_base::pattern()), _M_neg_format(money_base::pattern()), _M_allocated(false) @@ -955,7 +955,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param refs Passed to the base facet class. */ explicit - moneypunct(size_t __refs = 0) : facet(__refs), _M_data(NULL) + moneypunct(size_t __refs = 0) + : facet(__refs), _M_data(0) { _M_initialize_moneypunct(); } /** @@ -983,7 +984,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) */ explicit moneypunct(__c_locale __cloc, const char* __s, size_t __refs = 0) - : facet(__refs), _M_data(NULL) + : facet(__refs), _M_data(0) { _M_initialize_moneypunct(__cloc, __s); } /** @@ -1271,8 +1272,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // For use at construction time only. void - _M_initialize_moneypunct(__c_locale __cloc = NULL, - const char* __name = NULL); + _M_initialize_moneypunct(__c_locale __cloc = 0, + const char* __name = 0); }; template<typename _CharT, bool _Intl> diff --git a/libstdc++-v3/include/bits/locale_facets_nonio.tcc b/libstdc++-v3/include/bits/locale_facets_nonio.tcc index 48a913901e7..b5c77b9d7c0 100644 --- a/libstdc++-v3/include/bits/locale_facets_nonio.tcc +++ b/libstdc++-v3/include/bits/locale_facets_nonio.tcc @@ -44,7 +44,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) const locale::facet** __caches = __loc._M_impl->_M_caches; if (!__caches[__i]) { - __moneypunct_cache<_CharT, _Intl>* __tmp = NULL; + __moneypunct_cache<_CharT, _Intl>* __tmp = 0; __try { __tmp = new __moneypunct_cache<_CharT, _Intl>; diff --git a/libstdc++-v3/include/bits/move.h b/libstdc++-v3/include/bits/move.h index a137f982bed..98755dc7e57 100644 --- a/libstdc++-v3/include/bits/move.h +++ b/libstdc++-v3/include/bits/move.h @@ -31,7 +31,6 @@ #define _MOVE_H 1 #include <bits/c++config.h> -#include <cstddef> #include <bits/concept_check.h> _GLIBCXX_BEGIN_NAMESPACE(std) diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index 5a66bd6b2e2..690af186f96 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -828,27 +828,61 @@ namespace std operator()(_UniformRandomNumberGenerator& __urng, const param_type& __param) { - // XXX Must be fixed to work well for *arbitrary* __urng.max(), - // __urng.min(), __param.b(), __param.a(). Currently works fine only - // in the most common case __urng.max() - __urng.min() >= - // __param.b() - __param.a(), with __urng.max() > __urng.min() >= 0. typedef typename std::make_unsigned<typename - _UniformRandomNumberGenerator::result_type>::type __urntype; + _UniformRandomNumberGenerator::result_type>::type __urngtype; typedef typename std::make_unsigned<result_type>::type __utype; - typedef typename std::conditional<(sizeof(__urntype) > sizeof(__utype)), - __urntype, __utype>::type __uctype; + typedef typename std::conditional<(sizeof(__urngtype) + > sizeof(__utype)), + __urngtype, __utype>::type __uctype; - result_type __ret; + const __uctype __urngmin = __urng.min(); + const __uctype __urngmax = __urng.max(); + const __uctype __urngrange = __urngmax - __urngmin; + const __uctype __urange + = __uctype(__param.b()) - __uctype(__param.a()); - const __urntype __urnmin = __urng.min(); - const __urntype __urnmax = __urng.max(); - const __urntype __urnrange = __urnmax - __urnmin; - const __uctype __urange = __param.b() - __param.a(); - const __uctype __udenom = (__urnrange <= __urange - ? 1 : __urnrange / (__urange + 1)); - do - __ret = (__urntype(__urng()) - __urnmin) / __udenom; - while (__ret > __param.b() - __param.a()); + __uctype __ret; + + if (__urngrange > __urange) + { + // downscaling + const __uctype __uerange = __urange + 1; // __urange can be zero + const __uctype __scaling = __urngrange / __uerange; + const __uctype __past = __uerange * __scaling; + do + __ret = __uctype(__urng()) - __urngmin; + while (__ret >= __past); + __ret /= __scaling; + } + else if (__urngrange < __urange) + { + // upscaling + /* + Note that every value in [0, urange] + can be written uniquely as + + (urngrange + 1) * high + low + + where + + high in [0, urange / (urngrange + 1)] + + and + + low in [0, urngrange]. + */ + __uctype __tmp; // wraparound control + do + { + const __uctype __uerngrange = __urngrange + 1; + __tmp = (__uerngrange * operator() + (__urng, param_type(0, __urange / __uerngrange))); + __ret = __tmp + (__uctype(__urng()) - __urngmin); + } + while (__ret > __urange || __ret < __tmp); + } + else + __ret = __uctype(__urng()) - __urngmin; return __ret + __param.a(); } diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h new file mode 100644 index 00000000000..f035fd4ade4 --- /dev/null +++ b/libstdc++-v3/include/bits/regex.h @@ -0,0 +1,2428 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ + +/** + * @defgroup regex Regular Expressions + * A facility for performing regular expression pattern matching. + */ + //@{ + + // [7.7] Class regex_traits + /** + * @brief Describes aspects of a regular expression. + * + * A regular expression traits class that satisfies the requirements of + * section [28.7]. + * + * The class %regex is parameterized around a set of related types and + * functions used to complete the definition of its semantics. This class + * satisfies the requirements of such a traits class. + */ + template<typename _Ch_type> + struct regex_traits + { + public: + typedef _Ch_type char_type; + typedef std::basic_string<char_type> string_type; + typedef std::locale locale_type; + typedef std::ctype_base::mask char_class_type; + + public: + /** + * @brief Constructs a default traits object. + */ + regex_traits() + { } + + /** + * @brief Gives the length of a C-style string starting at @p __p. + * + * @param __p a pointer to the start of a character sequence. + * + * @returns the number of characters between @p *__p and the first + * default-initialized value of type @p char_type. In other words, uses + * the C-string algorithm for determining the length of a sequence of + * characters. + */ + static std::size_t + length(const char_type* __p) + { return string_type::traits_type::length(__p); } + + /** + * @brief Performs the identity translation. + * + * @param c A character to the locale-specific character set. + * + * @returns c. + */ + char_type + translate(char_type __c) const + { return __c; } + + /** + * @brief Translates a character into a case-insensitive equivalent. + * + * @param c A character to the locale-specific character set. + * + * @returns the locale-specific lower-case equivalent of c. + * @throws std::bad_cast if the imbued locale does not support the ctype + * facet. + */ + char_type + translate_nocase(char_type __c) const + { + using std::ctype; + using std::use_facet; + return use_facet<ctype<char_type> >(_M_locale).tolower(__c); + } + + /** + * @brief Gets a sort key for a character sequence. + * + * @param first beginning of the character sequence. + * @param last one-past-the-end of the character sequence. + * + * Returns a sort key for the character sequence designated by the + * iterator range [F1, F2) such that if the character sequence [G1, G2) + * sorts before the character sequence [H1, H2) then + * v.transform(G1, G2) < v.transform(H1, H2). + * + * What this really does is provide a more efficient way to compare a + * string to multiple other strings in locales with fancy collation + * rules and equivalence classes. + * + * @returns a locale-specific sort key equivalent to the input range. + * + * @throws std::bad_cast if the current locale does not have a collate + * facet. + */ + template<typename _Fwd_iter> + string_type + transform(_Fwd_iter __first, _Fwd_iter __last) const + { + using std::collate; + using std::use_facet; + const collate<_Ch_type>& __c(use_facet< + collate<_Ch_type> >(_M_locale)); + string_type __s(__first, __last); + return __c.transform(__s.data(), __s.data() + __s.size()); + } + + /** + * @brief Gets a sort key for a character sequence, independant of case. + * + * @param first beginning of the character sequence. + * @param last one-past-the-end of the character sequence. + * + * Effects: if typeid(use_facet<collate<_Ch_type> >) == + * typeid(collate_byname<_Ch_type>) and the form of the sort key + * returned by collate_byname<_Ch_type>::transform(first, last) is known + * and can be converted into a primary sort key then returns that key, + * otherwise returns an empty string. + * + * @todo Implement this function. + */ + template<typename _Fwd_iter> + string_type + transform_primary(_Fwd_iter __first, _Fwd_iter __last) const + { return string_type(); } + + /** + * @brief Gets a collation element by name. + * + * @param first beginning of the collation element name. + * @param last one-past-the-end of the collation element name. + * + * @returns a sequence of one or more characters that represents the + * collating element consisting of the character sequence designated by + * the iterator range [first, last). Returns an empty string if the + * character sequence is not a valid collating element. + * + * @todo Implement this function. + */ + template<typename _Fwd_iter> + string_type + lookup_collatename(_Fwd_iter __first, _Fwd_iter __last) const + { return string_type(); } + + /** + * @brief Maps one or more characters to a named character + * classification. + * + * @param first beginning of the character sequence. + * @param last one-past-the-end of the character sequence. + * @param icase ignores the case of the classification name. + * + * @returns an unspecified value that represents the character + * classification named by the character sequence designated by the + * iterator range [first, last). If @p icase is true, the returned mask + * identifies the classification regardless of the case of the characters + * to be matched (for example, [[:lower:]] is the same as [[:alpha:]]), + * otherwise a case-dependant classification is returned. The value + * returned shall be independent of the case of the characters in the + * character sequence. If the name is not recognized then returns a value + * that compares equal to 0. + * + * At least the following names (or their wide-character equivalent) are + * supported. + * - d + * - w + * - s + * - alnum + * - alpha + * - blank + * - cntrl + * - digit + * - graph + * - lower + * - print + * - punct + * - space + * - upper + * - xdigit + * + * @todo Implement this function. + */ + template<typename _Fwd_iter> + char_class_type + lookup_classname(_Fwd_iter __first, _Fwd_iter __last, + bool __icase = false) const + { return 0; } + + /** + * @brief Determines if @p c is a member of an identified class. + * + * @param c a character. + * @param f a class type (as returned from lookup_classname). + * + * @returns true if the character @p c is a member of the classification + * represented by @p f, false otherwise. + * + * @throws std::bad_cast if the current locale does not have a ctype + * facet. + */ + bool + isctype(_Ch_type __c, char_class_type __f) const; + + /** + * @brief Converts a digit to an int. + * + * @param ch a character representing a digit. + * @param radix the radix if the numeric conversion (limited to 8, 10, + * or 16). + * + * @returns the value represented by the digit ch in base radix if the + * character ch is a valid digit in base radix; otherwise returns -1. + */ + int + value(_Ch_type __ch, int __radix) const; + + /** + * @brief Imbues the regex_traits object with a copy of a new locale. + * + * @param loc A locale. + * + * @returns a copy of the previous locale in use by the regex_traits + * object. + * + * @note Calling imbue with a different locale than the one currently in + * use invalidates all cached data held by *this. + */ + locale_type + imbue(locale_type __loc) + { + std::swap(_M_locale, __loc); + return __loc; + } + + /** + * @brief Gets a copy of the current locale in use by the regex_traits + * object. + */ + locale_type + getloc() const + { return _M_locale; } + + protected: + locale_type _M_locale; + }; + + template<typename _Ch_type> + bool + regex_traits<_Ch_type>:: + isctype(_Ch_type __c, char_class_type __f) const + { + using std::ctype; + using std::use_facet; + const ctype<_Ch_type>& __ctype(use_facet< + ctype<_Ch_type> >(_M_locale)); + + if (__ctype.is(__c, __f)) + return true; + + // special case of underscore in [[:w:]] + if (__c == __ctype.widen('_')) + { + const char __wb[] = "w"; + char_class_type __wt = this->lookup_classname(__wb, + __wb + sizeof(__wb)); + if (__f | __wt) + return true; + } + + // special case of [[:space:]] in [[:blank:]] + if (__ctype.is(std::ctype_base::space, __c)) + { + const char __bb[] = "blank"; + char_class_type __bt = this->lookup_classname(__bb, + __bb + sizeof(__bb)); + if (__f | __bt) + return true; + } + + return false; + } + + template<typename _Ch_type> + int + regex_traits<_Ch_type>:: + value(_Ch_type __ch, int __radix) const + { + std::basic_istringstream<_Ch_type> __is(string_type(1, __ch)); + int __v; + if (__radix == 8) + __is >> std::oct; + else if (__radix == 16) + __is >> std::hex; + __is >> __v; + return __is.fail() ? -1 : __v; + } + + // [7.8] Class basic_regex + /** + * Objects of specializations of this class represent regular expressions + * constructed from sequences of character type @p _Ch_type. + * + * Storage for the regular expression is allocated and deallocated as + * necessary by the member functions of this class. + */ + template<typename _Ch_type, typename _Rx_traits = regex_traits<_Ch_type> > + class basic_regex + { + public: + // types: + typedef _Ch_type value_type; + typedef regex_constants::syntax_option_type flag_type; + typedef typename _Rx_traits::locale_type locale_type; + typedef typename _Rx_traits::string_type string_type; + + /** + * @name Constants + * std [28.8.1](1) + * @todo These should be constexpr. + */ + //@{ + static const regex_constants::syntax_option_type icase + = regex_constants::icase; + static const regex_constants::syntax_option_type nosubs + = regex_constants::nosubs; + static const regex_constants::syntax_option_type optimize + = regex_constants::optimize; + static const regex_constants::syntax_option_type collate + = regex_constants::collate; + static const regex_constants::syntax_option_type ECMAScript + = regex_constants::ECMAScript; + static const regex_constants::syntax_option_type basic + = regex_constants::basic; + static const regex_constants::syntax_option_type extended + = regex_constants::extended; + static const regex_constants::syntax_option_type awk + = regex_constants::awk; + static const regex_constants::syntax_option_type grep + = regex_constants::grep; + static const regex_constants::syntax_option_type egrep + = regex_constants::egrep; + //@} + + // [7.8.2] construct/copy/destroy + /** + * Constructs a basic regular expression that does not match any + * character sequence. + */ + basic_regex() + : _M_flags(regex_constants::ECMAScript), + _M_automaton(__regex::__compile<const _Ch_type*, _Rx_traits>(0, 0, + _M_traits, _M_flags)) + { } + + /** + * @brief Constructs a basic regular expression from the sequence + * [p, p + char_traits<_Ch_type>::length(p)) interpreted according to the + * flags in @p f. + * + * @param p A pointer to the start of a C-style null-terminated string + * containing a regular expression. + * @param f Flags indicating the syntax rules and options. + * + * @throws regex_error if @p p is not a valid regular expression. + */ + explicit + basic_regex(const _Ch_type* __p, + flag_type __f = regex_constants::ECMAScript) + : _M_flags(__f), + _M_automaton(__regex::__compile(__p, __p + _Rx_traits::length(__p), + _M_traits, _M_flags)) + { } + + /** + * @brief Constructs a basic regular expression from the sequence + * [p, p + len) interpreted according to the flags in @p f. + * + * @param p A pointer to the start of a string containing a regular + * expression. + * @param len The length of the string containing the regular expression. + * @param f Flags indicating the syntax rules and options. + * + * @throws regex_error if @p p is not a valid regular expression. + */ + basic_regex(const _Ch_type* __p, std::size_t __len, flag_type __f) + : _M_flags(__f), + _M_automaton(__regex::__compile(__p, __p + __len, _M_traits, _M_flags)) + { } + + /** + * @brief Copy-constructs a basic regular expression. + * + * @param rhs A @p regex object. + */ + basic_regex(const basic_regex& __rhs) + : _M_flags(__rhs._M_flags), _M_traits(__rhs._M_traits), + _M_automaton(__rhs._M_automaton) + { } + + /** + * @brief Move-constructs a basic regular expression. + * + * @param rhs A @p regex object. + */ + basic_regex(const basic_regex&& __rhs) + : _M_flags(__rhs._M_flags), _M_traits(__rhs._M_traits), + _M_automaton(std::move(__rhs._M_automaton)) + { } + + /** + * @brief Constructs a basic regular expression from the string + * @p s interpreted according to the flags in @p f. + * + * @param s A string containing a regular expression. + * @param f Flags indicating the syntax rules and options. + * + * @throws regex_error if @p s is not a valid regular expression. + */ + template<typename _Ch_traits, typename _Ch_alloc> + explicit + basic_regex(const std::basic_string<_Ch_type, _Ch_traits, + _Ch_alloc>& __s, + flag_type __f = regex_constants::ECMAScript) + : _M_flags(__f), + _M_automaton(__regex::__compile(__s.begin(), __s.end(), + _M_traits, _M_flags)) + { } + + /** + * @brief Constructs a basic regular expression from the range + * [first, last) interpreted according to the flags in @p f. + * + * @param first The start of a range containing a valid regular + * expression. + * @param last The end of a range containing a valid regular + * expression. + * @param f The format flags of the regular expression. + * + * @throws regex_error if @p [first, last) is not a valid regular + * expression. + */ + template<typename _InputIterator> + basic_regex(_InputIterator __first, _InputIterator __last, + flag_type __f = regex_constants::ECMAScript) + : _M_flags(__f), + _M_automaton(__regex::__compile(__first, __last, _M_traits, _M_flags)) + { } + + /** + * @brief Constructs a basic regular expression from an initializer list. + * + * @param l The initializer list. + * @param f The format flags of the regular expression. + * + * @throws regex_error if @p l is not a valid regular expression. + */ + basic_regex(initializer_list<_Ch_type> __l, + flag_type __f = regex_constants::ECMAScript) + : _M_flags(__f), + _M_automaton(__regex::__compile(__l.begin(), __l.end(), + _M_traits, _M_flags)) + { } + + /** + * @brief Destroys a basic regular expression. + */ + ~basic_regex() + { } + + /** + * @brief Assigns one regular expression to another. + */ + basic_regex& + operator=(const basic_regex& __rhs) + { return this->assign(__rhs); } + + /** + * @brief Move-assigns one regular expression to another. + */ + basic_regex& + operator=(basic_regex&& __rhs) + { return this->assign(std::move(__rhs)); } + + /** + * @brief Replaces a regular expression with a new one constructed from + * a C-style null-terminated string. + * + * @param A pointer to the start of a null-terminated C-style string + * containing a regular expression. + */ + basic_regex& + operator=(const _Ch_type* __p) + { return this->assign(__p, flags()); } + + /** + * @brief Replaces a regular expression with a new one constructed from + * a string. + * + * @param A pointer to a string containing a regular expression. + */ + template<typename _Ch_typeraits, typename _Allocator> + basic_regex& + operator=(const basic_string<_Ch_type, _Ch_typeraits, _Allocator>& __s) + { return this->assign(__s, flags()); } + + // [7.8.3] assign + /** + * @brief the real assignment operator. + * + * @param rhs Another regular expression object. + */ + basic_regex& + assign(const basic_regex& __rhs) + { + basic_regex __tmp(__rhs); + this->swap(__tmp); + return *this; + } + + /** + * @brief The move-assignment operator. + * + * @param rhs Another regular expression object. + */ + basic_regex& + assign(basic_regex&& __rhs) + { + basic_regex __tmp(std::move(__rhs)); + this->swap(__tmp); + return *this; + } + + /** + * @brief Assigns a new regular expression to a regex object from a + * C-style null-terminated string containing a regular expression + * pattern. + * + * @param p A pointer to a C-style null-terminated string containing + * a regular expression pattern. + * @param flags Syntax option flags. + * + * @throws regex_error if p does not contain a valid regular expression + * pattern interpreted according to @p flags. If regex_error is thrown, + * *this remains unchanged. + */ + basic_regex& + assign(const _Ch_type* __p, + flag_type __flags = regex_constants::ECMAScript) + { return this->assign(string_type(__p), __flags); } + + /** + * @brief Assigns a new regular expression to a regex object from a + * C-style string containing a regular expression pattern. + * + * @param p A pointer to a C-style string containing a + * regular expression pattern. + * @param len The length of the regular expression pattern string. + * @param flags Syntax option flags. + * + * @throws regex_error if p does not contain a valid regular expression + * pattern interpreted according to @p flags. If regex_error is thrown, + * *this remains unchanged. + */ + basic_regex& + assign(const _Ch_type* __p, std::size_t __len, flag_type __flags) + { return this->assign(string_type(__p, __len), __flags); } + + /** + * @brief Assigns a new regular expression to a regex object from a + * string containing a regular expression pattern. + * + * @param s A string containing a regular expression pattern. + * @param flags Syntax option flags. + * + * @throws regex_error if p does not contain a valid regular expression + * pattern interpreted according to @p flags. If regex_error is thrown, + * *this remains unchanged. + */ + template<typename _Ch_typeraits, typename _Allocator> + basic_regex& + assign(const basic_string<_Ch_type, _Ch_typeraits, _Allocator>& __s, + flag_type __f = regex_constants::ECMAScript) + { + basic_regex __tmp(__s, __f); + this->swap(__tmp); + return *this; + } + + /** + * @brief Assigns a new regular expression to a regex object. + * + * @param first The start of a range containing a valid regular + * expression. + * @param last The end of a range containing a valid regular + * expression. + * @param flags Syntax option flags. + * + * @throws regex_error if p does not contain a valid regular expression + * pattern interpreted according to @p flags. If regex_error is thrown, + * the object remains unchanged. + */ + template<typename _InputIterator> + basic_regex& + assign(_InputIterator __first, _InputIterator __last, + flag_type __flags = regex_constants::ECMAScript) + { return this->assign(string_type(__first, __last), __flags); } + + /** + * @brief Assigns a new regular expression to a regex object. + * + * @param l An initializer list representing a regular expression. + * @param flags Syntax option flags. + * + * @throws regex_error if @p l does not contain a valid regular + * expression pattern interpreted according to @p flags. If regex_error + * is thrown, the object remains unchanged. + */ + basic_regex& + assign(initializer_list<_Ch_type> __l, + flag_type __f = regex_constants::ECMAScript) + { return this->assign(__l.begin(), __l.end(), __f); } + + // [7.8.4] const operations + /** + * @brief Gets the number of marked subexpressions within the regular + * expression. + */ + unsigned int + mark_count() const + { return _M_automaton->_M_sub_count() - 1; } + + /** + * @brief Gets the flags used to construct the regular expression + * or in the last call to assign(). + */ + flag_type + flags() const + { return _M_flags; } + + // [7.8.5] locale + /** + * @brief Imbues the regular expression object with the given locale. + * + * @param loc A locale. + */ + locale_type + imbue(locale_type __loc) + { return _M_traits.imbue(__loc); } + + /** + * @brief Gets the locale currently imbued in the regular expression + * object. + */ + locale_type + getloc() const + { return _M_traits.getloc(); } + + // [7.8.6] swap + /** + * @brief Swaps the contents of two regular expression objects. + * + * @param rhs Another regular expression object. + */ + void + swap(basic_regex& __rhs) + { + std::swap(_M_flags, __rhs._M_flags); + std::swap(_M_traits, __rhs._M_traits); + std::swap(_M_automaton, __rhs._M_automaton); + } + +#ifdef _GLIBCXX_DEBUG + void + _M_dot(std::ostream& __ostr) + { _M_automaton->_M_dot(__ostr); } +#endif + + const __regex::_AutomatonPtr& + _M_get_automaton() const + { return _M_automaton; } + + protected: + flag_type _M_flags; + _Rx_traits _M_traits; + __regex::_AutomatonPtr _M_automaton; + }; + + /** @brief Standard regular expressions. */ + typedef basic_regex<char> regex; +#ifdef _GLIBCXX_USE_WCHAR_T + /** @brief Standard wide-character regular expressions. */ + typedef basic_regex<wchar_t> wregex; +#endif + + + // [7.8.6] basic_regex swap + /** + * @brief Swaps the contents of two regular expression objects. + * @param lhs First regular expression. + * @param rhs Second regular expression. + */ + template<typename _Ch_type, typename _Rx_traits> + inline void + swap(basic_regex<_Ch_type, _Rx_traits>& __lhs, + basic_regex<_Ch_type, _Rx_traits>& __rhs) + { __lhs.swap(__rhs); } + + + // [7.9] Class template sub_match + /** + * A sequence of characters matched by a particular marked sub-expression. + * + * An object of this class is essentially a pair of iterators marking a + * matched subexpression within a regular expression pattern match. Such + * objects can be converted to and compared with std::basic_string objects + * of a similar base character type as the pattern matched by the regular + * expression. + * + * The iterators that make up the pair are the usual half-open interval + * referencing the actual original pattern matched. + */ + template<typename _BiIter> + class sub_match : public std::pair<_BiIter, _BiIter> + { + public: + typedef typename iterator_traits<_BiIter>::value_type value_type; + typedef typename iterator_traits<_BiIter>::difference_type + difference_type; + typedef _BiIter iterator; + typedef std::basic_string<value_type> string_type; + + public: + bool matched; + + /** + * Gets the length of the matching sequence. + */ + difference_type + length() const + { return this->matched ? std::distance(this->first, this->second) : 0; } + + /** + * @brief Gets the matching sequence as a string. + * + * @returns the matching sequence as a string. + * + * This is the implicit conversion operator. It is identical to the + * str() member function except that it will want to pop up in + * unexpected places and cause a great deal of confusion and cursing + * from the unwary. + */ + operator string_type() const + { + return this->matched + ? string_type(this->first, this->second) + : string_type(); + } + + /** + * @brief Gets the matching sequence as a string. + * + * @returns the matching sequence as a string. + */ + string_type + str() const + { + return this->matched + ? string_type(this->first, this->second) + : string_type(); + } + + /** + * @brief Compares this and another matched sequence. + * + * @param s Another matched sequence to compare to this one. + * + * @retval <0 this matched sequence will collate before @p s. + * @retval =0 this matched sequence is equivalent to @p s. + * @retval <0 this matched sequence will collate after @p s. + */ + int + compare(const sub_match& __s) const + { return this->str().compare(__s.str()); } + + /** + * @brief Compares this sub_match to a string. + * + * @param s A string to compare to this sub_match. + * + * @retval <0 this matched sequence will collate before @p s. + * @retval =0 this matched sequence is equivalent to @p s. + * @retval <0 this matched sequence will collate after @p s. + */ + int + compare(const string_type& __s) const + { return this->str().compare(__s); } + + /** + * @brief Compares this sub_match to a C-style string. + * + * @param s A C-style string to compare to this sub_match. + * + * @retval <0 this matched sequence will collate before @p s. + * @retval =0 this matched sequence is equivalent to @p s. + * @retval <0 this matched sequence will collate after @p s. + */ + int + compare(const value_type* __s) const + { return this->str().compare(__s); } + }; + + + /** @brief Standard regex submatch over a C-style null-terminated string. */ + typedef sub_match<const char*> csub_match; + /** @brief Standard regex submatch over a standard string. */ + typedef sub_match<string::const_iterator> ssub_match; +#ifdef _GLIBCXX_USE_WCHAR_T + /** @brief Regex submatch over a C-style null-terminated wide string. */ + typedef sub_match<const wchar_t*> wcsub_match; + /** @brief Regex submatch over a standard wide string. */ + typedef sub_match<wstring::const_iterator> wssub_match; +#endif + + // [7.9.2] sub_match non-member operators + + /** + * @brief Tests the equivalence of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator==(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) == 0; } + + /** + * @brief Tests the inequivalence of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator!=(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) != 0; } + + /** + * @brief Tests the ordering of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator<(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) < 0; } + + /** + * @brief Tests the ordering of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator<=(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) <= 0; } + + /** + * @brief Tests the ordering of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator>=(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) >= 0; } + + /** + * @brief Tests the ordering of two regular expression submatches. + * @param lhs First regular expression submatch. + * @param rhs Second regular expression submatch. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _BiIter> + inline bool + operator>(const sub_match<_BiIter>& __lhs, + const sub_match<_BiIter>& __rhs) + { return __lhs.compare(__rhs) > 0; } + + /** + * @brief Tests the equivalence of a string and a regular expression + * submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator==(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs == __rhs.str(); } + + /** + * @brief Tests the inequivalence of a string and a regular expression + * submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator!=(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs) + { return __lhs != __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator<(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs) + { return __lhs < __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator>(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs) + { return __lhs > __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator>=(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs) + { return __lhs >= __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator<=(const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __lhs, const sub_match<_Bi_iter>& __rhs) + { return __lhs <= __rhs.str(); } + + /** + * @brief Tests the equivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator==(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() == __rhs; } + + /** + * @brief Tests the inequivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc> + inline bool + operator!=(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() != __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc> + inline bool + operator<(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() < __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc> + inline bool + operator>(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() > __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc> + inline bool + operator>=(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() >= __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc> + inline bool + operator<=(const sub_match<_Bi_iter>& __lhs, + const basic_string< + typename iterator_traits<_Bi_iter>::value_type, + _Ch_traits, _Ch_alloc>& __rhs) + { return __lhs.str() <= __rhs; } + + /** + * @brief Tests the equivalence of a C string and a regular expression + * submatch. + * @param lhs A C string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs == __rhs.str(); } + + /** + * @brief Tests the inequivalence of an iterator value and a regular + * expression submatch. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs != __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs < __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs > __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>=(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs >= __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<=(typename iterator_traits<_Bi_iter>::value_type const* __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs <= __rhs.str(); } + + /** + * @brief Tests the equivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A pointer to a string? + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator==(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() == __rhs; } + + /** + * @brief Tests the inequivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A pointer to a string. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator!=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() != __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() < __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() > __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() >= __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A string. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const* __rhs) + { return __lhs.str() <= __rhs; } + + /** + * @brief Tests the equivalence of a string and a regular expression + * submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs == __rhs.str(); } + + /** + * @brief Tests the inequivalence of a string and a regular expression + * submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs != __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs < __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs > __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>=(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs >= __rhs.str(); } + + /** + * @brief Tests the ordering of a string and a regular expression submatch. + * @param lhs A string. + * @param rhs A regular expression submatch. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<=(typename iterator_traits<_Bi_iter>::value_type const& __lhs, + const sub_match<_Bi_iter>& __rhs) + { return __lhs <= __rhs.str(); } + + /** + * @brief Tests the equivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs is equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator==(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() == __rhs; } + + /** + * @brief Tests the inequivalence of a regular expression submatch and a + * string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs is not equivalent to @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator!=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() != __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs precedes @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() < __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs succeeds @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() > __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs does not precede @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator>=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() >= __rhs; } + + /** + * @brief Tests the ordering of a regular expression submatch and a string. + * @param lhs A regular expression submatch. + * @param rhs A const string reference. + * @returns true if @a lhs does not succeed @a rhs, false otherwise. + */ + template<typename _Bi_iter> + inline bool + operator<=(const sub_match<_Bi_iter>& __lhs, + typename iterator_traits<_Bi_iter>::value_type const& __rhs) + { return __lhs.str() <= __rhs; } + + /** + * @brief Inserts a matched string into an output stream. + * + * @param os The output stream. + * @param m A submatch string. + * + * @returns the output stream with the submatch string inserted. + */ + template<typename _Ch_type, typename _Ch_traits, typename _Bi_iter> + inline + basic_ostream<_Ch_type, _Ch_traits>& + operator<<(basic_ostream<_Ch_type, _Ch_traits>& __os, + const sub_match<_Bi_iter>& __m) + { return __os << __m.str(); } + + // [7.10] Class template match_results + + /* + * Special sub_match object representing an unmatched sub-expression. + */ + template<typename _Bi_iter> + inline const sub_match<_Bi_iter>& + __unmatched_sub() + { + static const sub_match<_Bi_iter> __unmatched = sub_match<_Bi_iter>(); + return __unmatched; + } + + /** + * @brief The results of a match or search operation. + * + * A collection of character sequences representing the result of a regular + * expression match. Storage for the collection is allocated and freed as + * necessary by the member functions of class template match_results. + * + * This class satisfies the Sequence requirements, with the exception that + * only the operations defined for a const-qualified Sequence are supported. + * + * The sub_match object stored at index 0 represents sub-expression 0, i.e. + * the whole match. In this case the %sub_match member matched is always true. + * The sub_match object stored at index n denotes what matched the marked + * sub-expression n within the matched expression. If the sub-expression n + * participated in a regular expression match then the %sub_match member + * matched evaluates to true, and members first and second denote the range + * of characters [first, second) which formed that match. Otherwise matched + * is false, and members first and second point to the end of the sequence + * that was searched. + * + * @nosubgrouping + */ + template<typename _Bi_iter, + typename _Allocator = allocator<sub_match<_Bi_iter> > > + class match_results + : private std::vector<std::sub_match<_Bi_iter>, _Allocator> + { + private: + /* + * The vector base is empty if this does not represent a successful match. + * Otherwise it contains n+3 elements where n is the number of marked + * sub-expressions: + * [0] entire match + * [1] 1st marked subexpression + * ... + * [n] nth marked subexpression + * [n+1] prefix + * [n+2] suffix + */ + typedef std::vector<std::sub_match<_Bi_iter>, _Allocator> + _Base_type; + + public: + /** + * @name 10.? Public Types + */ + //@{ + typedef sub_match<_Bi_iter> value_type; + typedef const value_type& const_reference; + typedef const_reference reference; + typedef typename _Base_type::const_iterator const_iterator; + typedef const_iterator iterator; + typedef typename std::iterator_traits<_Bi_iter>::difference_type + difference_type; + /* TODO: needs allocator_traits */ + typedef typename _Allocator::size_type size_type; + typedef _Allocator allocator_type; + typedef typename std::iterator_traits<_Bi_iter>::value_type + char_type; + typedef std::basic_string<char_type> string_type; + //@} + + public: + /** + * @name 10.1 Construction, Copying, and Destruction + */ + //@{ + + /** + * @brief Constructs a default %match_results container. + * @post size() returns 0 and str() returns an empty string. + */ + explicit + match_results(const _Allocator& __a = _Allocator()) + : _Base_type(__a) + { } + + /** + * @brief Copy constructs a %match_results. + */ + match_results(const match_results& __rhs) + : _Base_type(__rhs) + { } + + /** + * @brief Assigns rhs to *this. + */ + match_results& + operator=(const match_results __rhs) + { + match_results(__rhs).swap(*this); + return *this; + } + + /** + * @brief Destroys a %match_results object. + */ + ~match_results() + { } + + //@} + + /** + * @name 10.2 Size + */ + //@{ + + /** + * @brief Gets the number of matches and submatches. + * + * The number of matches for a given regular expression will be either 0 + * if there was no match or mark_count() + 1 if a match was successful. + * Some matches may be empty. + * + * @returns the number of matches found. + */ + size_type + size() const + { + size_type __size = _Base_type::size(); + return (__size && _Base_type::operator[](0).matched) ? __size - 2 : 0; + } + + size_type + max_size() const + { return _Base_type::max_size(); } + + /** + * @brief Indicates if the %match_results contains no results. + * @retval true The %match_results object is empty. + * @retval false The %match_results object is not empty. + */ + bool + empty() const + { return _Base_type::empty(); } + + //@} + + /** + * @name 10.3 Element Access + */ + //@{ + + /** + * @brief Gets the length of the indicated submatch. + * @param sub indicates the submatch. + * + * This function returns the length of the indicated submatch, or the + * length of the entire match if @p sub is zero (the default). + */ + difference_type + length(size_type __sub = 0) const + { return this[__sub].length(); } + + /** + * @brief Gets the offset of the beginning of the indicated submatch. + * @param sub indicates the submatch. + * + * This function returns the offset from the beginning of the target + * sequence to the beginning of the submatch, unless the value of @p sub + * is zero (the default), in which case this function returns the offset + * from the beginning of the target sequence to the beginning of the + * match. + * + * Returns -1 if @p sub is out of range. + */ + difference_type + position(size_type __sub = 0) const + { + return __sub < size() ? std::distance(this->prefix().first, + (*this)[__sub].first) : -1; + } + + /** + * @brief Gets the match or submatch converted to a string type. + * @param sub indicates the submatch. + * + * This function gets the submatch (or match, if @p sub is zero) extracted + * from the target range and converted to the associated string type. + */ + string_type + str(size_type __sub = 0) const + { return (*this)[__sub].str(); } + + /** + * @brief Gets a %sub_match reference for the match or submatch. + * @param sub indicates the submatch. + * + * This function gets a reference to the indicated submatch, or the entire + * match if @p sub is zero. + * + * If @p sub >= size() then this function returns a %sub_match with a + * special value indicating no submatch. + */ + const_reference + operator[](size_type __sub) const + { + return __sub < size() + ? _Base_type::operator[](__sub) + : __unmatched_sub<_Bi_iter>(); + } + + /** + * @brief Gets a %sub_match representing the match prefix. + * + * This function gets a reference to a %sub_match object representing the + * part of the target range between the start of the target range and the + * start of the match. + */ + const_reference + prefix() const + { + return !empty() + ? _Base_type::operator[](_Base_type::size() - 2) + : __unmatched_sub<_Bi_iter>(); + } + + /** + * @brief Gets a %sub_match representing the match suffix. + * + * This function gets a reference to a %sub_match object representing the + * part of the target range between the end of the match and the end of + * the target range. + */ + const_reference + suffix() const + { + return !empty() + ? _Base_type::operator[](_Base_type::size() - 1) + : __unmatched_sub<_Bi_iter>(); + } + + /** + * @brief Gets an iterator to the start of the %sub_match collection. + */ + const_iterator + begin() const + { return _Base_type::begin(); } + + /** + * @brief Gets an iterator to the start of the %sub_match collection. + */ + const_iterator + cbegin() const + { return _Base_type::cbegin(); } + + /** + * @brief Gets an iterator to one-past-the-end of the collection. + */ + const_iterator + end() const + { + return !empty() + ? _Base_type::end() - 2 + : _Base_type::end(); + } + + /** + * @brief Gets an iterator to one-past-the-end of the collection. + */ + const_iterator + cend() const + { + return !empty() + ? _Base_type::cend() - 2 + : _Base_type::cend(); + } + + //@} + + /** + * @name 10.4 Formatting + * + * These functions perform formatted substitution of the matched character + * sequences into their target. The format specifiers and escape sequences + * accepted by these functions are determined by their @p flags parameter + * as documented above. + */ + //@{ + + /** + * @todo Implement this function. + */ + template<typename _Out_iter> + _Out_iter + format(_Out_iter __out, const string_type& __fmt, + regex_constants::match_flag_type __flags + = regex_constants::format_default) const + { return __out; } + + /** + * @todo Implement this function. + */ + string_type + format(const string_type& __fmt, + regex_constants::match_flag_type __flags + = regex_constants::format_default) const; + + //@} + + /** + * @name 10.5 Allocator + */ + //@{ + + /** + * @brief Gets a copy of the allocator. + */ + allocator_type + get_allocator() const + { return _Base_type::get_allocator(); } + + //@} + + /** + * @name 10.6 Swap + */ + //@{ + + /** + * @brief Swaps the contents of two match_results. + */ + void + swap(match_results& __that) + { _Base_type::swap(__that); } + //@} + + private: + friend class __regex::_SpecializedResults<_Bi_iter, _Allocator>; + }; + + typedef match_results<const char*> cmatch; + typedef match_results<string::const_iterator> smatch; +#ifdef _GLIBCXX_USE_WCHAR_T + typedef match_results<const wchar_t*> wcmatch; + typedef match_results<wstring::const_iterator> wsmatch; +#endif + + // match_results comparisons + /** + * @brief Compares two match_results for equality. + * @returns true if the two objects refer to the same match, + * false otherwise. + * @todo Implement this function. + */ + template<typename _Bi_iter, typename _Allocator> + inline bool + operator==(const match_results<_Bi_iter, _Allocator>& __m1, + const match_results<_Bi_iter, _Allocator>& __m2); + + /** + * @brief Compares two match_results for inequality. + * @returns true if the two objects do not refer to the same match, + * false otherwise. + */ + template<typename _Bi_iter, class _Allocator> + inline bool + operator!=(const match_results<_Bi_iter, _Allocator>& __m1, + const match_results<_Bi_iter, _Allocator>& __m2) + { return !(__m1 == __m2); } + + // [7.10.6] match_results swap + /** + * @brief Swaps two match results. + * @param lhs A match result. + * @param rhs A match result. + * + * The contents of the two match_results objects are swapped. + */ + template<typename _Bi_iter, typename _Allocator> + inline void + swap(match_results<_Bi_iter, _Allocator>& __lhs, + match_results<_Bi_iter, _Allocator>& __rhs) + { __lhs.swap(__rhs); } + + // [7.11.2] Function template regex_match + /** + * @name Matching, Searching, and Replacing + */ + //@{ + + /** + * @brief Determines if there is a match between the regular expression @p e + * and all of the character sequence [first, last). + * + * @param s Start of the character sequence to match. + * @param e One-past-the-end of the character sequence to match. + * @param m The match results. + * @param re The regular expression. + * @param flags Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + * + * @todo Implement this function. + */ + template<typename _Bi_iter, typename _Allocator, + typename _Ch_type, typename _Rx_traits> + bool + regex_match(_Bi_iter __s, + _Bi_iter __e, + match_results<_Bi_iter, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { + __regex::_AutomatonPtr __a = __re._M_get_automaton(); + __regex::_Automaton::_SizeT __sz = __a->_M_sub_count(); + __regex::_SpecializedCursor<_Bi_iter> __cs(__s, __e); + __regex::_SpecializedResults<_Bi_iter, _Allocator> __r(__sz, __cs, __m); + __regex::_Grep_matcher __matcher(__cs, __r, __a, __flags); + return __m[0].matched; + } + + /** + * @brief Indicates if there is a match between the regular expression @p e + * and all of the character sequence [first, last). + * + * @param first Beginning of the character sequence to match. + * @param last One-past-the-end of the character sequence to match. + * @param re The regular expression. + * @param flags Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + */ + template<typename _Bi_iter, typename _Ch_type, typename _Rx_traits> + bool + regex_match(_Bi_iter __first, _Bi_iter __last, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { + match_results<_Bi_iter> __what; + return regex_match(__first, __last, __what, __re, __flags); + } + + /** + * @brief Determines if there is a match between the regular expression @p e + * and a C-style null-terminated string. + * + * @param s The C-style null-terminated string to match. + * @param m The match results. + * @param re The regular expression. + * @param f Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_type, typename _Allocator, typename _Rx_traits> + inline bool + regex_match(const _Ch_type* __s, + match_results<const _Ch_type*, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __f + = regex_constants::match_default) + { return regex_match(__s, __s + _Rx_traits::length(__s), __m, __re, __f); } + + /** + * @brief Determines if there is a match between the regular expression @p e + * and a string. + * + * @param s The string to match. + * @param m The match results. + * @param re The regular expression. + * @param flags Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_traits, typename _Ch_alloc, + typename _Allocator, typename _Ch_type, typename _Rx_traits> + inline bool + regex_match(const basic_string<_Ch_type, _Ch_traits, _Ch_alloc>& __s, + match_results<typename basic_string<_Ch_type, + _Ch_traits, _Ch_alloc>::const_iterator, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { return regex_match(__s.begin(), __s.end(), __m, __re, __flags); } + + /** + * @brief Indicates if there is a match between the regular expression @p e + * and a C-style null-terminated string. + * + * @param s The C-style null-terminated string to match. + * @param re The regular expression. + * @param f Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_type, class _Rx_traits> + inline bool + regex_match(const _Ch_type* __s, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __f + = regex_constants::match_default) + { return regex_match(__s, __s + _Rx_traits::length(__s), __re, __f); } + + /** + * @brief Indicates if there is a match between the regular expression @p e + * and a string. + * + * @param s [IN] The string to match. + * @param re [IN] The regular expression. + * @param flags [IN] Controls how the regular expression is matched. + * + * @retval true A match exists. + * @retval false Otherwise. + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_traits, typename _Str_allocator, + typename _Ch_type, typename _Rx_traits> + inline bool + regex_match(const basic_string<_Ch_type, _Ch_traits, _Str_allocator>& __s, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { return regex_match(__s.begin(), __s.end(), __re, __flags); } + + // [7.11.3] Function template regex_search + /** + * Searches for a regular expression within a range. + * @param first [IN] The start of the string to search. + * @param last [IN] One-past-the-end of the string to search. + * @param m [OUT] The match results. + * @param re [IN] The regular expression to search for. + * @param flags [IN] Search policy flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string, the content of %m is + * undefined. + * + * @throws an exception of type regex_error. + * + * @todo Implement this function. + */ + template<typename _Bi_iter, typename _Allocator, + typename _Ch_type, typename _Rx_traits> + inline bool + regex_search(_Bi_iter __first, _Bi_iter __last, + match_results<_Bi_iter, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { return false; } + + /** + * Searches for a regular expression within a range. + * @param first [IN] The start of the string to search. + * @param last [IN] One-past-the-end of the string to search. + * @param re [IN] The regular expression to search for. + * @param flags [IN] Search policy flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string. + * @doctodo + * + * @throws an exception of type regex_error. + */ + template<typename _Bi_iter, typename _Ch_type, typename _Rx_traits> + inline bool + regex_search(_Bi_iter __first, _Bi_iter __last, + const basic_regex<_Ch_type, _Rx_traits>& __re, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { + match_results<_Bi_iter> __what; + return regex_search(__first, __last, __what, __re, __flags); + } + + /** + * @brief Searches for a regular expression within a C-string. + * @param s [IN] A C-string to search for the regex. + * @param m [OUT] The set of regex matches. + * @param e [IN] The regex to search for in @p s. + * @param f [IN] The search flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string, the content of %m is + * undefined. + * @doctodo + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_type, class _Allocator, class _Rx_traits> + inline bool + regex_search(const _Ch_type* __s, + match_results<const _Ch_type*, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __e, + regex_constants::match_flag_type __f + = regex_constants::match_default) + { return regex_search(__s, __s + _Rx_traits::length(__s), __m, __e, __f); } + + /** + * @brief Searches for a regular expression within a C-string. + * @param s [IN] The C-string to search. + * @param e [IN] The regular expression to search for. + * @param f [IN] Search policy flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string. + * @doctodo + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_type, typename _Rx_traits> + inline bool + regex_search(const _Ch_type* __s, + const basic_regex<_Ch_type, _Rx_traits>& __e, + regex_constants::match_flag_type __f + = regex_constants::match_default) + { return regex_search(__s, __s + _Rx_traits::length(__s), __e, __f); } + + /** + * @brief Searches for a regular expression within a string. + * @param s [IN] The string to search. + * @param e [IN] The regular expression to search for. + * @param flags [IN] Search policy flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string. + * @doctodo + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_traits, typename _String_allocator, + typename _Ch_type, typename _Rx_traits> + inline bool + regex_search(const basic_string<_Ch_type, _Ch_traits, + _String_allocator>& __s, + const basic_regex<_Ch_type, _Rx_traits>& __e, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { return regex_search(__s.begin(), __s.end(), __e, __flags); } + + /** + * @brief Searches for a regular expression within a string. + * @param s [IN] A C++ string to search for the regex. + * @param m [OUT] The set of regex matches. + * @param e [IN] The regex to search for in @p s. + * @param f [IN] The search flags. + * @retval true A match was found within the string. + * @retval false No match was found within the string, the content of %m is + * undefined. + * + * @throws an exception of type regex_error. + */ + template<typename _Ch_traits, typename _Ch_alloc, + typename _Allocator, typename _Ch_type, + typename _Rx_traits> + inline bool + regex_search(const basic_string<_Ch_type, _Ch_traits, _Ch_alloc>& __s, + match_results<typename basic_string<_Ch_type, + _Ch_traits, _Ch_alloc>::const_iterator, _Allocator>& __m, + const basic_regex<_Ch_type, _Rx_traits>& __e, + regex_constants::match_flag_type __f + = regex_constants::match_default) + { return regex_search(__s.begin(), __s.end(), __m, __e, __f); } + + // std [28.11.4] Function template regex_replace + /** + * @doctodo + * @param out + * @param first + * @param last + * @param e + * @param fmt + * @param flags + * + * @returns out + * @throws an exception of type regex_error. + * + * @todo Implement this function. + */ + template<typename _Out_iter, typename _Bi_iter, + typename _Rx_traits, typename _Ch_type> + inline _Out_iter + regex_replace(_Out_iter __out, _Bi_iter __first, _Bi_iter __last, + const basic_regex<_Ch_type, _Rx_traits>& __e, + const basic_string<_Ch_type>& __fmt, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { return __out; } + + /** + * @doctodo + * @param s + * @param e + * @param fmt + * @param flags + * + * @returns a copy of string @p s with replacements. + * + * @throws an exception of type regex_error. + */ + template<typename _Rx_traits, typename _Ch_type> + inline basic_string<_Ch_type> + regex_replace(const basic_string<_Ch_type>& __s, + const basic_regex<_Ch_type, _Rx_traits>& __e, + const basic_string<_Ch_type>& __fmt, + regex_constants::match_flag_type __flags + = regex_constants::match_default) + { + std::string __result; + regex_replace(std::back_inserter(__result), + __s.begin(), __s.end(), __e, __fmt, __flags); + return __result; + } + + //@} + + // std [28.12] Class template regex_iterator + /** + * An iterator adaptor that will provide repeated calls of regex_search over + * a range until no more matches remain. + */ + template<typename _Bi_iter, + typename _Ch_type = typename iterator_traits<_Bi_iter>::value_type, + typename _Rx_traits = regex_traits<_Ch_type> > + class regex_iterator + { + public: + typedef basic_regex<_Ch_type, _Rx_traits> regex_type; + typedef match_results<_Bi_iter> value_type; + typedef std::ptrdiff_t difference_type; + typedef const value_type* pointer; + typedef const value_type& reference; + typedef std::forward_iterator_tag iterator_category; + + public: + /** + * @brief Provides a singular iterator, useful for indicating + * one-past-the-end of a range. + * @todo Implement this function. + * @doctodo + */ + regex_iterator(); + + /** + * Constructs a %regex_iterator... + * @param a [IN] The start of a text range to search. + * @param b [IN] One-past-the-end of the text range to search. + * @param re [IN] The regular expression to match. + * @param m [IN] Policy flags for match rules. + * @todo Implement this function. + * @doctodo + */ + regex_iterator(_Bi_iter __a, _Bi_iter __b, const regex_type& __re, + regex_constants::match_flag_type __m + = regex_constants::match_default); + + /** + * Copy constructs a %regex_iterator. + * @todo Implement this function. + * @doctodo + */ + regex_iterator(const regex_iterator& __rhs); + + /** + * @todo Implement this function. + * @doctodo + */ + regex_iterator& + operator=(const regex_iterator& __rhs); + + /** + * @todo Implement this function. + * @doctodo + */ + bool + operator==(const regex_iterator& __rhs); + + /** + * @todo Implement this function. + * @doctodo + */ + bool + operator!=(const regex_iterator& __rhs); + + /** + * @todo Implement this function. + * @doctodo + */ + const value_type& + operator*(); + + /** + * @todo Implement this function. + * @doctodo + */ + const value_type* + operator->(); + + /** + * @todo Implement this function. + * @doctodo + */ + regex_iterator& + operator++(); + + /** + * @todo Implement this function. + * @doctodo + */ + regex_iterator + operator++(int); + + private: + // these members are shown for exposition only: + _Bi_iter begin; + _Bi_iter end; + const regex_type* pregex; + regex_constants::match_flag_type flags; + match_results<_Bi_iter> match; + }; + + typedef regex_iterator<const char*> cregex_iterator; + typedef regex_iterator<string::const_iterator> sregex_iterator; +#ifdef _GLIBCXX_USE_WCHAR_T + typedef regex_iterator<const wchar_t*> wcregex_iterator; + typedef regex_iterator<wstring::const_iterator> wsregex_iterator; +#endif + + // [7.12.2] Class template regex_token_iterator + /** + * Iterates over submatches in a range (or @a splits a text string). + * + * The purpose of this iterator is to enumerate all, or all specified, + * matches of a regular expression within a text range. The dereferenced + * value of an iterator of this class is a std::sub_match object. + */ + template<typename _Bi_iter, + typename _Ch_type = typename iterator_traits<_Bi_iter>::value_type, + typename _Rx_traits = regex_traits<_Ch_type> > + class regex_token_iterator + { + public: + typedef basic_regex<_Ch_type, _Rx_traits> regex_type; + typedef sub_match<_Bi_iter> value_type; + typedef std::ptrdiff_t difference_type; + typedef const value_type* pointer; + typedef const value_type& reference; + typedef std::forward_iterator_tag iterator_category; + + public: + /** + * @brief Default constructs a %regex_token_iterator. + * @todo Implement this function. + * + * A default-constructed %regex_token_iterator is a singular iterator + * that will compare equal to the one-past-the-end value for any + * iterator of the same type. + */ + regex_token_iterator(); + + /** + * Constructs a %regex_token_iterator... + * @param a [IN] The start of the text to search. + * @param b [IN] One-past-the-end of the text to search. + * @param re [IN] The regular expression to search for. + * @param submatch [IN] Which submatch to return. There are some + * special values for this parameter: + * - -1 each enumerated subexpression does NOT + * match the regular expression (aka field + * splitting) + * - 0 the entire string matching the + * subexpression is returned for each match + * within the text. + * - >0 enumerates only the indicated + * subexpression from a match within the text. + * @param m [IN] Policy flags for match rules. + * + * @todo Implement this function. + * @doctodo + */ + regex_token_iterator(_Bi_iter __a, _Bi_iter __b, const regex_type& __re, + int __submatch = 0, + regex_constants::match_flag_type __m + = regex_constants::match_default); + + /** + * Constructs a %regex_token_iterator... + * @param a [IN] The start of the text to search. + * @param b [IN] One-past-the-end of the text to search. + * @param re [IN] The regular expression to search for. + * @param submatches [IN] A list of subexpressions to return for each + * regular expression match within the text. + * @param m [IN] Policy flags for match rules. + * + * @todo Implement this function. + * @doctodo + */ + regex_token_iterator(_Bi_iter __a, _Bi_iter __b, + const regex_type& __re, + const std::vector<int>& __submatches, + regex_constants::match_flag_type __m + = regex_constants::match_default); + + /** + * Constructs a %regex_token_iterator... + * @param a [IN] The start of the text to search. + * @param b [IN] One-past-the-end of the text to search. + * @param re [IN] The regular expression to search for. + * @param submatches [IN] A list of subexpressions to return for each + * regular expression match within the text. + * @param m [IN] Policy flags for match rules. + + * @todo Implement this function. + * @doctodo + */ + template<std::size_t _Nm> + regex_token_iterator(_Bi_iter __a, _Bi_iter __b, + const regex_type& __re, + const int (&__submatches)[_Nm], + regex_constants::match_flag_type __m + = regex_constants::match_default); + + /** + * @brief Copy constructs a %regex_token_iterator. + * @param rhs [IN] A %regex_token_iterator to copy. + * @todo Implement this function. + */ + regex_token_iterator(const regex_token_iterator& __rhs); + + /** + * @brief Assigns a %regex_token_iterator to another. + * @param rhs [IN] A %regex_token_iterator to copy. + * @todo Implement this function. + */ + regex_token_iterator& + operator=(const regex_token_iterator& __rhs); + + /** + * @brief Compares a %regex_token_iterator to another for equality. + * @todo Implement this function. + */ + bool + operator==(const regex_token_iterator& __rhs); + + /** + * @brief Compares a %regex_token_iterator to another for inequality. + * @todo Implement this function. + */ + bool + operator!=(const regex_token_iterator& __rhs); + + /** + * @brief Dereferences a %regex_token_iterator. + * @todo Implement this function. + */ + const value_type& + operator*(); + + /** + * @brief Selects a %regex_token_iterator member. + * @todo Implement this function. + */ + const value_type* + operator->(); + + /** + * @brief Increments a %regex_token_iterator. + * @todo Implement this function. + */ + regex_token_iterator& + operator++(); + + /** + * @brief Postincrements a %regex_token_iterator. + * @todo Implement this function. + */ + regex_token_iterator + operator++(int); + + private: // data members for exposition only: + typedef regex_iterator<_Bi_iter, _Ch_type, _Rx_traits> position_iterator; + + position_iterator __position; + const value_type* __result; + value_type __suffix; + std::size_t __n; + std::vector<int> __subs; + }; + + /** @brief Token iterator for C-style NULL-terminated strings. */ + typedef regex_token_iterator<const char*> cregex_token_iterator; + /** @brief Token iterator for standard strings. */ + typedef regex_token_iterator<string::const_iterator> sregex_token_iterator; +#ifdef _GLIBCXX_USE_WCHAR_T + /** @brief Token iterator for C-style NULL-terminated wide strings. */ + typedef regex_token_iterator<const wchar_t*> wcregex_token_iterator; + /** @brief Token iterator for standard wide-character strings. */ + typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator; +#endif + + //@} // group regex + +} + diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h new file mode 100644 index 00000000000..0bc362dc77e --- /dev/null +++ b/libstdc++-v3/include/bits/regex_compiler.h @@ -0,0 +1,1115 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_parser.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ +namespace __regex +{ + struct _Scanner_base + { + // FIXME: replace these constanst with constexpr + typedef unsigned int _StateT; + + static const _StateT _S_state_at_start = 1 << 0; + static const _StateT _S_state_in_brace = 1 << 2; + static const _StateT _S_state_in_bracket = 1 << 3; + }; + + // + // @brief Scans an input range for regex tokens. + // + // The %_Scanner class interprets the regular expression pattern in the input + // range passed to its constructor as a sequence of parse tokens passed to + // the regular expression compiler. The sequence of tokens provided depends + // on the flag settings passed to the constructor: different regular + // expression gramars will interpret the same input pattern in syntactically + // different ways. + // + template<typename _InputIterator> + class _Scanner: public _Scanner_base + { + public: + typedef _InputIterator _IteratorT; + typedef typename std::iterator_traits<_IteratorT>::value_type _CharT; + typedef std::basic_string<_CharT> _StringT; + typedef regex_constants::syntax_option_type _FlagT; + typedef const std::ctype<_CharT> _CtypeT; + + // Token types returned from the scanner. + enum _TokenT + { + _S_token_anychar, + _S_token_backref, + _S_token_bracket_begin, + _S_token_bracket_end, + _S_token_inverse_class, + _S_token_char_class_name, + _S_token_closure0, + _S_token_closure1, + _S_token_collelem_multi, + _S_token_collelem_single, + _S_token_collsymbol, + _S_token_comma, + _S_token_dash, + _S_token_dup_count, + _S_token_eof, + _S_token_equiv_class_name, + _S_token_interval_begin, + _S_token_interval_end, + _S_token_line_begin, + _S_token_line_end, + _S_token_opt, + _S_token_or, + _S_token_ord_char, + _S_token_quoted_char, + _S_token_subexpr_begin, + _S_token_subexpr_end, + _S_token_word_begin, + _S_token_word_end, + _S_token_unknown + }; + + public: + _Scanner(_IteratorT __begin, _IteratorT __end, _FlagT __flags, + std::locale __loc) + : _M_current(__begin) , _M_end(__end) , _M_flags(__flags), + _M_ctype(std::use_facet<_CtypeT>(__loc)), _M_state(_S_state_at_start) + { _M_advance(); } + + void + _M_advance(); + + _TokenT + _M_token() const + { return _M_curToken; } + + const _StringT& + _M_value() const + { return _M_curValue; } + +#ifdef _GLIBCXX_DEBUG + std::ostream& + _M_print(std::ostream&); +#endif + + private: + void + _M_eat_escape(); + + void + _M_scan_in_brace(); + + void + _M_scan_in_bracket(); + + void + _M_eat_charclass(); + + void + _M_eat_equivclass(); + + void + _M_eat_collsymbol(); + + private: + _IteratorT _M_current; + _IteratorT _M_end; + _FlagT _M_flags; + _CtypeT& _M_ctype; + _TokenT _M_curToken; + _StringT _M_curValue; + _StateT _M_state; + }; + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_advance() + { + if (_M_current == _M_end) + { + _M_curToken = _S_token_eof; + return; + } + + _CharT __c = *_M_current; + if (_M_state & _S_state_in_bracket) + { + _M_scan_in_bracket(); + return; + } + if (_M_state & _S_state_in_brace) + { + _M_scan_in_brace(); + return; + } + else if (_M_state & _S_state_at_start && __c == _M_ctype.widen('^')) + { + _M_curToken = _S_token_line_begin; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('$')) + { + _M_curToken = _S_token_line_end; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('.')) + { + _M_curToken = _S_token_anychar; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('*')) + { + _M_curToken = _S_token_closure0; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('+')) + { + _M_curToken = _S_token_closure1; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('|')) + { + _M_curToken = _S_token_or; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('[')) + { + _M_curToken = _S_token_bracket_begin; + _M_state |= (_S_state_in_bracket | _S_state_at_start); + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('\\')) + { + _M_eat_escape(); + return; + } + else if (!(_M_flags & (regex_constants::basic | regex_constants::grep))) + { + if (__c == _M_ctype.widen('(')) + { + _M_curToken = _S_token_subexpr_begin; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen(')')) + { + _M_curToken = _S_token_subexpr_end; + ++_M_current; + return; + } + else if (__c == _M_ctype.widen('{')) + { + _M_curToken = _S_token_interval_begin; + _M_state |= _S_state_in_brace; + ++_M_current; + return; + } + } + + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + ++_M_current; + } + + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_scan_in_brace() + { + if (_M_ctype.is(_CtypeT::digit, *_M_current)) + { + _M_curToken = _S_token_dup_count; + _M_curValue.assign(1, *_M_current); + ++_M_current; + while (_M_current != _M_end + && _M_ctype.is(_CtypeT::digit, *_M_current)) + { + _M_curValue += *_M_current; + ++_M_current; + } + return; + } + else if (*_M_current == _M_ctype.widen(',')) + { + _M_curToken = _S_token_comma; + ++_M_current; + return; + } + if (_M_flags & (regex_constants::basic | regex_constants::grep)) + { + if (*_M_current == _M_ctype.widen('\\')) + _M_eat_escape(); + } + else + { + if (*_M_current == _M_ctype.widen('}')) + { + _M_curToken = _S_token_interval_end; + _M_state &= ~_S_state_in_brace; + ++_M_current; + return; + } + } + } + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_scan_in_bracket() + { + if (_M_state & _S_state_at_start && *_M_current == _M_ctype.widen('^')) + { + _M_curToken = _S_token_inverse_class; + _M_state &= ~_S_state_at_start; + ++_M_current; + return; + } + else if (*_M_current == _M_ctype.widen('[')) + { + ++_M_current; + if (_M_current == _M_end) + { + _M_curToken = _S_token_eof; + return; + } + + if (*_M_current == _M_ctype.widen('.')) + { + _M_curToken = _S_token_collsymbol; + _M_eat_collsymbol(); + return; + } + else if (*_M_current == _M_ctype.widen(':')) + { + _M_curToken = _S_token_char_class_name; + _M_eat_charclass(); + return; + } + else if (*_M_current == _M_ctype.widen('=')) + { + _M_curToken = _S_token_equiv_class_name; + _M_eat_equivclass(); + return; + } + } + else if (*_M_current == _M_ctype.widen('-')) + { + _M_curToken = _S_token_dash; + ++_M_current; + return; + } + else if (*_M_current == _M_ctype.widen(']')) + { + if (!(_M_flags & regex_constants::ECMAScript) + || !(_M_state & _S_state_at_start)) + { + // special case: only if _not_ chr first after + // '[' or '[^' and if not ECMAscript + _M_curToken = _S_token_bracket_end; + ++_M_current; + return; + } + } + _M_curToken = _S_token_collelem_single; + _M_curValue.assign(1, *_M_current); + ++_M_current; + } + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_eat_escape() + { + ++_M_current; + if (_M_current == _M_end) + { + _M_curToken = _S_token_eof; + return; + } + _CharT __c = *_M_current; + ++_M_current; + + if (__c == _M_ctype.widen('(')) + { + if (!(_M_flags & (regex_constants::basic | regex_constants::grep))) + { + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + } + else + _M_curToken = _S_token_subexpr_begin; + } + else if (__c == _M_ctype.widen(')')) + { + if (!(_M_flags & (regex_constants::basic | regex_constants::grep))) + { + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + } + else + _M_curToken = _S_token_subexpr_end; + } + else if (__c == _M_ctype.widen('{')) + { + if (!(_M_flags & (regex_constants::basic | regex_constants::grep))) + { + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + } + else + { + _M_curToken = _S_token_interval_begin; + _M_state |= _S_state_in_brace; + } + } + else if (__c == _M_ctype.widen('}')) + { + if (!(_M_flags & (regex_constants::basic | regex_constants::grep))) + { + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + } + else + { + if (!(_M_state && _S_state_in_brace)) + __throw_regex_error(regex_constants::error_badbrace); + _M_state &= ~_S_state_in_brace; + _M_curToken = _S_token_interval_end; + } + } + else if (__c == _M_ctype.widen('x')) + { + ++_M_current; + if (_M_current == _M_end) + { + _M_curToken = _S_token_eof; + return; + } + if (_M_ctype.is(_CtypeT::digit, *_M_current)) + { + _M_curValue.assign(1, *_M_current); + ++_M_current; + if (_M_current == _M_end) + { + _M_curToken = _S_token_eof; + return; + } + if (_M_ctype.is(_CtypeT::digit, *_M_current)) + { + _M_curValue += *_M_current; + ++_M_current; + return; + } + } + } + else if (__c == _M_ctype.widen('^') + || __c == _M_ctype.widen('.') + || __c == _M_ctype.widen('*') + || __c == _M_ctype.widen('$') + || __c == _M_ctype.widen('\\')) + { + _M_curToken = _S_token_ord_char; + _M_curValue.assign(1, __c); + } + else if (_M_ctype.is(_CtypeT::digit, __c)) + { + _M_curToken = _S_token_backref; + _M_curValue.assign(1, __c); + } + else + __throw_regex_error(regex_constants::error_escape); + } + + + // Eats a character class or throwns an exception. + // current point to ':' delimiter on entry, char after ']' on return + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_eat_charclass() + { + ++_M_current; // skip ':' + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_ctype); + for (_M_curValue.clear(); + _M_current != _M_end && *_M_current != _M_ctype.widen(':'); + ++_M_current) + _M_curValue += *_M_current; + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_ctype); + ++_M_current; // skip ':' + if (*_M_current != _M_ctype.widen(']')) + __throw_regex_error(regex_constants::error_ctype); + ++_M_current; // skip ']' + } + + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_eat_equivclass() + { + ++_M_current; // skip '=' + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_collate); + for (_M_curValue.clear(); + _M_current != _M_end && *_M_current != _M_ctype.widen('='); + ++_M_current) + _M_curValue += *_M_current; + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_collate); + ++_M_current; // skip '=' + if (*_M_current != _M_ctype.widen(']')) + __throw_regex_error(regex_constants::error_collate); + ++_M_current; // skip ']' + } + + + template<typename _InputIterator> + void + _Scanner<_InputIterator>:: + _M_eat_collsymbol() + { + ++_M_current; // skip '.' + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_collate); + for (_M_curValue.clear(); + _M_current != _M_end && *_M_current != _M_ctype.widen('.'); + ++_M_current) + _M_curValue += *_M_current; + if (_M_current == _M_end) + __throw_regex_error(regex_constants::error_collate); + ++_M_current; // skip '.' + if (*_M_current != _M_ctype.widen(']')) + __throw_regex_error(regex_constants::error_collate); + ++_M_current; // skip ']' + } + +#ifdef _GLIBCXX_DEBUG + template<typename _InputIterator> + std::ostream& + _Scanner<_InputIterator>:: + _M_print(std::ostream& ostr) + { + switch (_M_curToken) + { + case _S_token_anychar: + ostr << "any-character\n"; + break; + case _S_token_backref: + ostr << "backref\n"; + break; + case _S_token_bracket_begin: + ostr << "bracket-begin\n"; + break; + case _S_token_bracket_end: + ostr << "bracket-end\n"; + break; + case _S_token_char_class_name: + ostr << "char-class-name \"" << _M_curValue << "\"\n"; + break; + case _S_token_closure0: + ostr << "closure0\n"; + break; + case _S_token_closure1: + ostr << "closure1\n"; + break; + case _S_token_collelem_multi: + ostr << "coll-elem-multi \"" << _M_curValue << "\"\n"; + break; + case _S_token_collelem_single: + ostr << "coll-elem-single \"" << _M_curValue << "\"\n"; + break; + case _S_token_collsymbol: + ostr << "collsymbol \"" << _M_curValue << "\"\n"; + break; + case _S_token_comma: + ostr << "comma\n"; + break; + case _S_token_dash: + ostr << "dash\n"; + break; + case _S_token_dup_count: + ostr << "dup count: " << _M_curValue << "\n"; + break; + case _S_token_eof: + ostr << "EOF\n"; + break; + case _S_token_equiv_class_name: + ostr << "equiv-class-name \"" << _M_curValue << "\"\n"; + break; + case _S_token_interval_begin: + ostr << "interval begin\n"; + break; + case _S_token_interval_end: + ostr << "interval end\n"; + break; + case _S_token_line_begin: + ostr << "line begin\n"; + break; + case _S_token_line_end: + ostr << "line end\n"; + break; + case _S_token_opt: + ostr << "opt\n"; + break; + case _S_token_or: + ostr << "or\n"; + break; + case _S_token_ord_char: + ostr << "ordinary character: \"" << _M_value() << "\"\n"; + break; + case _S_token_quoted_char: + ostr << "quoted char\n"; + break; + case _S_token_subexpr_begin: + ostr << "subexpr begin\n"; + break; + case _S_token_subexpr_end: + ostr << "subexpr end\n"; + break; + case _S_token_word_begin: + ostr << "word begin\n"; + break; + case _S_token_word_end: + ostr << "word end\n"; + break; + case _S_token_unknown: + ostr << "-- unknown token --\n"; + break; + } + return ostr; + } +#endif + + // Builds an NFA from an input iterator interval. + template<typename _InIter, typename _TraitsT> + class _Compiler + { + public: + typedef _InIter _IterT; + typedef typename std::iterator_traits<_InIter>::value_type _CharT; + typedef std::basic_string<_CharT> _StringT; + typedef regex_constants::syntax_option_type _FlagT; + + public: + _Compiler(const _InIter& __b, const _InIter& __e, + _TraitsT& __traits, _FlagT __flags); + + const _Nfa& + _M_nfa() const + { return _M_state_store; } + + private: + typedef _Scanner<_InIter> _ScannerT; + typedef typename _ScannerT::_TokenT _TokenT; + typedef std::stack<_StateSeq, std::vector<_StateSeq> > _StackT; + typedef _RangeMatcher<_InIter, _TraitsT> _RMatcherT; + + // accepts a specific token or returns false. + bool + _M_match_token(_TokenT __token); + + void + _M_disjunction(); + + bool + _M_alternative(); + + bool + _M_term(); + + bool + _M_assertion(); + + bool + _M_quantifier(); + + bool + _M_atom(); + + bool + _M_bracket_expression(); + + bool + _M_bracket_list(_RMatcherT& __matcher); + + bool + _M_follow_list(_RMatcherT& __matcher); + + bool + _M_follow_list2(_RMatcherT& __matcher); + + bool + _M_expression_term(_RMatcherT& __matcher); + + bool + _M_range_expression(_RMatcherT& __matcher); + + bool + _M_start_range(_RMatcherT& __matcher); + + bool + _M_collating_symbol(_RMatcherT& __matcher); + + bool + _M_equivalence_class(_RMatcherT& __matcher); + + bool + _M_character_class(_RMatcherT& __matcher); + + int + _M_cur_int_value(int __radix); + + private: + _TraitsT& _M_traits; + _ScannerT _M_scanner; + _StringT _M_cur_value; + _Nfa _M_state_store; + _StackT _M_stack; + }; + + template<typename _InIter, typename _TraitsT> + _Compiler<_InIter, _TraitsT>:: + _Compiler(const _InIter& __b, const _InIter& __e, _TraitsT& __traits, + _Compiler<_InIter, _TraitsT>::_FlagT __flags) + : _M_traits(__traits), _M_scanner(__b, __e, __flags, _M_traits.getloc()), + _M_state_store(__flags) + { + using std::bind; + using std::placeholders::_1; + using std::placeholders::_2; + typedef _StartTagger<_InIter, _TraitsT> _Start; + typedef _EndTagger<_InIter, _TraitsT> _End; + + _StateSeq __r(_M_state_store, + _M_state_store._M_insert_subexpr_begin( + bind(_Start(0), _1, _2))); + _M_disjunction(); + if (!_M_stack.empty()) + { + __r._M_append(_M_stack.top()); + _M_stack.pop(); + } + __r._M_append(_M_state_store. + _M_insert_subexpr_end(0, bind(_End(0), _1, _2))); + __r._M_append(_M_state_store._M_insert_accept()); + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_match_token(_Compiler<_InIter, _TraitsT>::_TokenT token) + { + if (token == _M_scanner._M_token()) + { + _M_cur_value = _M_scanner._M_value(); + _M_scanner._M_advance(); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + void + _Compiler<_InIter, _TraitsT>:: + _M_disjunction() + { + this->_M_alternative(); + if (_M_match_token(_ScannerT::_S_token_or)) + { + _StateSeq __alt1 = _M_stack.top(); _M_stack.pop(); + this->_M_disjunction(); + _StateSeq __alt2 = _M_stack.top(); _M_stack.pop(); + _M_stack.push(_StateSeq(__alt1, __alt2)); + } + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_alternative() + { + if (this->_M_term()) + { + _StateSeq __re = _M_stack.top(); _M_stack.pop(); + this->_M_alternative(); + if (!_M_stack.empty()) + { + __re._M_append(_M_stack.top()); + _M_stack.pop(); + } + _M_stack.push(__re); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_term() + { + if (this->_M_assertion()) + return true; + if (this->_M_atom()) + { + this->_M_quantifier(); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_assertion() + { + if (_M_match_token(_ScannerT::_S_token_line_begin)) + { + // __m.push(_Matcher::_S_opcode_line_begin); + return true; + } + if (_M_match_token(_ScannerT::_S_token_line_end)) + { + // __m.push(_Matcher::_S_opcode_line_end); + return true; + } + if (_M_match_token(_ScannerT::_S_token_word_begin)) + { + // __m.push(_Matcher::_S_opcode_word_begin); + return true; + } + if (_M_match_token(_ScannerT::_S_token_word_end)) + { + // __m.push(_Matcher::_S_opcode_word_end); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_quantifier() + { + if (_M_match_token(_ScannerT::_S_token_closure0)) + { + if (_M_stack.empty()) + __throw_regex_error(regex_constants::error_badrepeat); + _StateSeq __r(_M_stack.top(), -1); + __r._M_append(__r._M_front()); + _M_stack.pop(); + _M_stack.push(__r); + return true; + } + if (_M_match_token(_ScannerT::_S_token_closure1)) + { + if (_M_stack.empty()) + __throw_regex_error(regex_constants::error_badrepeat); + _StateSeq __r(_M_state_store, + _M_state_store. + _M_insert_alt(_S_invalid_state_id, + _M_stack.top()._M_front())); + _M_stack.top()._M_append(__r); + return true; + } + if (_M_match_token(_ScannerT::_S_token_opt)) + { + if (_M_stack.empty()) + __throw_regex_error(regex_constants::error_badrepeat); + _StateSeq __r(_M_stack.top(), -1); + _M_stack.pop(); + _M_stack.push(__r); + return true; + } + if (_M_match_token(_ScannerT::_S_token_interval_begin)) + { + if (_M_stack.empty()) + __throw_regex_error(regex_constants::error_badrepeat); + if (!_M_match_token(_ScannerT::_S_token_dup_count)) + __throw_regex_error(regex_constants::error_badbrace); + _StateSeq __r(_M_stack.top()); + int __min_rep = _M_cur_int_value(10); + for (int __i = 1; __i < __min_rep; ++__i) + _M_stack.top()._M_append(__r._M_clone()); + if (_M_match_token(_ScannerT::_S_token_comma)) + if (_M_match_token(_ScannerT::_S_token_dup_count)) + { + int __n = _M_cur_int_value(10) - __min_rep; + if (__n < 0) + __throw_regex_error(regex_constants::error_badbrace); + for (int __i = 0; __i < __n; ++__i) + { + _StateSeq __r(_M_state_store, + _M_state_store. + _M_insert_alt(_S_invalid_state_id, + _M_stack.top()._M_front())); + _M_stack.top()._M_append(__r); + } + } + else + { + _StateSeq __r(_M_stack.top(), -1); + __r._M_push_back(__r._M_front()); + _M_stack.pop(); + _M_stack.push(__r); + } + if (!_M_match_token(_ScannerT::_S_token_interval_end)) + __throw_regex_error(regex_constants::error_brace); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_atom() + { + using std::bind; + using std::placeholders::_1; + using std::placeholders::_2; + typedef _CharMatcher<_InIter, _TraitsT> _CMatcher; + typedef _StartTagger<_InIter, _TraitsT> _Start; + typedef _EndTagger<_InIter, _TraitsT> _End; + + if (_M_match_token(_ScannerT::_S_token_anychar)) + { + _M_stack.push(_StateSeq(_M_state_store, + _M_state_store. + _M_insert_matcher(bind(_AnyMatcher, _1)))); + return true; + } + if (_M_match_token(_ScannerT::_S_token_ord_char)) + { + _M_stack.push(_StateSeq + (_M_state_store, _M_state_store. + _M_insert_matcher + (bind(_CMatcher(_M_cur_value[0], _M_traits), _1)))); + return true; + } + if (_M_match_token(_ScannerT::_S_token_quoted_char)) + { + // note that in the ECMA grammar, this case covers backrefs. + _M_stack.push(_StateSeq(_M_state_store, + _M_state_store. + _M_insert_matcher + (bind(_CMatcher(_M_cur_value[0], _M_traits), + _1)))); + return true; + } + if (_M_match_token(_ScannerT::_S_token_backref)) + { + // __m.push(_Matcher::_S_opcode_ordchar, _M_cur_value); + return true; + } + if (_M_match_token(_ScannerT::_S_token_subexpr_begin)) + { + int __mark = _M_state_store._M_sub_count(); + _StateSeq __r(_M_state_store, + _M_state_store. + _M_insert_subexpr_begin(bind(_Start(__mark), _1, _2))); + this->_M_disjunction(); + if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) + __throw_regex_error(regex_constants::error_paren); + if (!_M_stack.empty()) + { + __r._M_append(_M_stack.top()); + _M_stack.pop(); + } + __r._M_append(_M_state_store._M_insert_subexpr_end + (__mark, bind(_End(__mark), _1, _2))); + _M_stack.push(__r); + return true; + } + return _M_bracket_expression(); + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_bracket_expression() + { + using std::bind; + using std::placeholders::_1; + if (_M_match_token(_ScannerT::_S_token_bracket_begin)) + { + _RMatcherT __matcher(_M_match_token(_ScannerT::_S_token_line_begin), + _M_traits); + if (!_M_bracket_list(__matcher) + || !_M_match_token(_ScannerT::_S_token_bracket_end)) + __throw_regex_error(regex_constants::error_brack); + _M_stack.push(_StateSeq(_M_state_store, + _M_state_store._M_insert_matcher + (bind(__matcher, _1)))); + return true; + } + return false; + } + + // If the dash is the last character in the bracket expression, it is not + // special. + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_bracket_list(_RMatcherT& __matcher) + { + if (_M_follow_list(__matcher)) + { + if (_M_match_token(_ScannerT::_S_token_dash)) + __matcher._M_add_char(_M_cur_value[0]); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_follow_list(_RMatcherT& __matcher) + { return _M_expression_term(__matcher) && _M_follow_list2(__matcher); } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_follow_list2(_RMatcherT& __matcher) + { + if (_M_expression_term(__matcher)) + return _M_follow_list2(__matcher); + return true; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_expression_term(_RMatcherT& __matcher) + { + return (_M_collating_symbol(__matcher) + || _M_character_class(__matcher) + || _M_equivalence_class(__matcher) + || (_M_start_range(__matcher) + && _M_range_expression(__matcher))); + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_range_expression(_RMatcherT& __matcher) + { + if (!_M_collating_symbol(__matcher)) + if (!_M_match_token(_ScannerT::_S_token_dash)) + __throw_regex_error(regex_constants::error_range); + __matcher._M_make_range(); + return true; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_start_range(_RMatcherT& __matcher) + { return _M_match_token(_ScannerT::_S_token_dash); } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_collating_symbol(_RMatcherT& __matcher) + { + if (_M_match_token(_ScannerT::_S_token_collelem_single)) + { + __matcher._M_add_char(_M_cur_value[0]); + return true; + } + if (_M_match_token(_ScannerT::_S_token_collsymbol)) + { + __matcher._M_add_collating_element(_M_cur_value); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_equivalence_class(_RMatcherT& __matcher) + { + if (_M_match_token(_ScannerT::_S_token_equiv_class_name)) + { + __matcher._M_add_equivalence_class(_M_cur_value); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + bool + _Compiler<_InIter, _TraitsT>:: + _M_character_class(_RMatcherT& __matcher) + { + if (_M_match_token(_ScannerT::_S_token_char_class_name)) + { + __matcher._M_add_character_class(_M_cur_value); + return true; + } + return false; + } + + template<typename _InIter, typename _TraitsT> + int + _Compiler<_InIter, _TraitsT>:: + _M_cur_int_value(int __radix) + { + int __v = 0; + for (typename _StringT::size_type __i = 0; + __i < _M_cur_value.length(); ++__i) + __v =__v * __radix + _M_traits.value(_M_cur_value[__i], __radix); + return __v; + } + + template<typename _InIter, typename _TraitsT> + _AutomatonPtr + __compile(const _InIter& __b, const _InIter& __e, _TraitsT& __t, + regex_constants::syntax_option_type __f) + { return _AutomatonPtr(new _Nfa(_Compiler<_InIter, _TraitsT>(__b, __e, __t, + __f)._M_nfa())); } + +} // namespace __regex +} // namespace std + +/* vim: set ts=8 sw=2 sts=2: */ diff --git a/libstdc++-v3/include/bits/regex_constants.h b/libstdc++-v3/include/bits/regex_constants.h new file mode 100644 index 00000000000..787b88b8cd4 --- /dev/null +++ b/libstdc++-v3/include/bits/regex_constants.h @@ -0,0 +1,299 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_constants + * @brief Constant definitions for the std regex library. + * + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ + +/** + * @namespace std::regex_constants + * @brief ISO C++-0x entities sub namespace for regex. + */ +namespace regex_constants +{ + /** + * @name 5.1 Regular Expression Syntax Options + */ + //@{ + enum __syntax_option + { + _S_icase, + _S_nosubs, + _S_optimize, + _S_collate, + _S_ECMAScript, + _S_basic, + _S_extended, + _S_awk, + _S_grep, + _S_egrep, + _S_syntax_last + }; + + /** + * @brief This is a bitmask type indicating how to interpret the regex. + * + * The @c syntax_option_type is implementation defined but it is valid to + * perform bitwise operations on these values and expect the right thing to + * happen. + * + * A valid value of type syntax_option_type shall have exactly one of the + * elements @c ECMAScript, @c basic, @c extended, @c awk, @c grep, @c egrep + * %set. + */ + typedef unsigned int syntax_option_type; + + /** + * Specifies that the matching of regular expressions against a character + * sequence shall be performed without regard to case. + */ + static const syntax_option_type icase = 1 << _S_icase; + + /** + * Specifies that when a regular expression is matched against a character + * container sequence, no sub-expression matches are to be stored in the + * supplied match_results structure. + */ + static const syntax_option_type nosubs = 1 << _S_nosubs; + + /** + * Specifies that the regular expression engine should pay more attention to + * the speed with which regular expressions are matched, and less to the + * speed with which regular expression objects are constructed. Otherwise + * it has no detectable effect on the program output. + */ + static const syntax_option_type optimize = 1 << _S_optimize; + + /** + * Specifies that character ranges of the form [a-b] should be locale + * sensitive. + */ + static const syntax_option_type collate = 1 << _S_collate; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by ECMAScript in ECMA-262 [Ecma International, ECMAScript + * Language Specification, Standard Ecma-262, third edition, 1999], as + * modified in section [28.13]. This grammar is similar to that defined + * in the PERL scripting language but extended with elements found in the + * POSIX regular expression grammar. + */ + static const syntax_option_type ECMAScript = 1 << _S_ECMAScript; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by POSIX basic regular expressions in IEEE Std 1003.1-2001, + * Portable Operating System Interface (POSIX), Base Definitions and + * Headers, Section 9, Regular Expressions [IEEE, Information Technology -- + * Portable Operating System Interface (POSIX), IEEE Standard 1003.1-2001]. + */ + static const syntax_option_type basic = 1 << _S_basic; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by POSIX extended regular expressions in IEEE Std 1003.1-2001, + * Portable Operating System Interface (POSIX), Base Definitions and Headers, + * Section 9, Regular Expressions. + */ + static const syntax_option_type extended = 1 << _S_extended; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by POSIX utility awk in IEEE Std 1003.1-2001. This option is + * identical to syntax_option_type extended, except that C-style escape + * sequences are supported. These sequences are: + * \\\\, \\a, \\b, \\f, \\n, \\r, \\t , \\v, \\', ', + * and \\ddd (where ddd is one, two, or three octal digits). + */ + static const syntax_option_type awk = 1 << _S_awk; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by POSIX utility grep in IEEE Std 1003.1-2001. This option is + * identical to syntax_option_type basic, except that newlines are treated + * as whitespace. + */ + static const syntax_option_type grep = 1 << _S_grep; + + /** + * Specifies that the grammar recognized by the regular expression engine is + * that used by POSIX utility grep when given the -E option in + * IEEE Std 1003.1-2001. This option is identical to syntax_option_type + * extended, except that newlines are treated as whitespace. + */ + static const syntax_option_type egrep = 1 << _S_egrep; + + //@} + + /** + * @name 5.2 Matching Rules + * + * Matching a regular expression against a sequence of characters [first, + * last) proceeds according to the rules of the grammar specified for the + * regular expression object, modified according to the effects listed + * below for any bitmask elements set. + * + */ + //@{ + + enum __match_flag + { + _S_not_bol, + _S_not_eol, + _S_not_bow, + _S_not_eow, + _S_any, + _S_not_null, + _S_continuous, + _S_prev_avail, + _S_sed, + _S_no_copy, + _S_first_only, + _S_match_flag_last + }; + + /** + * @brief This is a bitmask type indicating regex matching rules. + * + * The @c match_flag_type is implementation defined but it is valid to + * perform bitwise operations on these values and expect the right thing to + * happen. + */ + typedef std::bitset<_S_match_flag_last> match_flag_type; + + /** + * The default matching rules. + */ + static const match_flag_type match_default = 0; + + /** + * The first character in the sequence [first, last) is treated as though it + * is not at the beginning of a line, so the character (^) in the regular + * expression shall not match [first, first). + */ + static const match_flag_type match_not_bol = 1 << _S_not_bol; + + /** + * The last character in the sequence [first, last) is treated as though it + * is not at the end of a line, so the character ($) in the regular + * expression shall not match [last, last). + */ + static const match_flag_type match_not_eol = 1 << _S_not_eol; + + /** + * The expression \\b is not matched against the sub-sequence + * [first,first). + */ + static const match_flag_type match_not_bow = 1 << _S_not_bow; + + /** + * The expression \\b should not be matched against the sub-sequence + * [last,last). + */ + static const match_flag_type match_not_eow = 1 << _S_not_eow; + + /** + * If more than one match is possible then any match is an acceptable + * result. + */ + static const match_flag_type match_any = 1 << _S_any; + + /** + * The expression does not match an empty sequence. + */ + static const match_flag_type match_not_null = 1 << _S_not_null; + + /** + * The expression only matches a sub-sequence that begins at first . + */ + static const match_flag_type match_continuous = 1 << _S_continuous; + + /** + * --first is a valid iterator position. When this flag is set then the + * flags match_not_bol and match_not_bow are ignored by the regular + * expression algorithms 7.11 and iterators 7.12. + */ + static const match_flag_type match_prev_avail = 1 << _S_prev_avail; + + /** + * When a regular expression match is to be replaced by a new string, the + * new string is constructed using the rules used by the ECMAScript replace + * function in ECMA- 262 [Ecma International, ECMAScript Language + * Specification, Standard Ecma-262, third edition, 1999], part 15.5.4.11 + * String.prototype.replace. In addition, during search and replace + * operations all non-overlapping occurrences of the regular expression + * are located and replaced, and sections of the input that did not match + * the expression are copied unchanged to the output string. + * + * Format strings (from ECMA-262 [15.5.4.11]): + * @li $$ The dollar-sign itself ($) + * @li $& The matched substring. + * @li $` The portion of @a string that precedes the matched substring. + * This would be match_results::prefix(). + * @li $' The portion of @a string that follows the matched substring. + * This would be match_results::suffix(). + * @li $n The nth capture, where n is in [1,9] and $n is not followed by a + * decimal digit. If n <= match_results::size() and the nth capture + * is undefined, use the empty string instead. If n > + * match_results::size(), the result is implementation-defined. + * @li $nn The nnth capture, where nn is a two-digit decimal number on + * [01, 99]. If nn <= match_results::size() and the nth capture is + * undefined, use the empty string instead. If + * nn > match_results::size(), the result is implementation-defined. + */ + static const match_flag_type format_default = 0; + + /** + * When a regular expression match is to be replaced by a new string, the + * new string is constructed using the rules used by the POSIX sed utility + * in IEEE Std 1003.1- 2001 [IEEE, Information Technology -- Portable + * Operating System Interface (POSIX), IEEE Standard 1003.1-2001]. + */ + static const match_flag_type format_sed = 1 << _S_sed; + + /** + * During a search and replace operation, sections of the character + * container sequence being searched that do not match the regular + * expression shall not be copied to the output string. + */ + static const match_flag_type format_no_copy = 1 << _S_no_copy; + + /** + * When specified during a search and replace operation, only the first + * occurrence of the regular expression shall be replaced. + */ + static const match_flag_type format_first_only = 1 << _S_first_only; + + //@} + +} // namespace regex_constants +} // namespace std + diff --git a/libstdc++-v3/include/bits/regex_cursor.h b/libstdc++-v3/include/bits/regex_cursor.h new file mode 100644 index 00000000000..e8330fb7885 --- /dev/null +++ b/libstdc++-v3/include/bits/regex_cursor.h @@ -0,0 +1,92 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_cursor.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ +namespace __regex +{ + // ABC for pattern matching + struct _PatternCursor + { + virtual ~_PatternCursor() { }; + virtual void _M_next() = 0; + virtual bool _M_at_end() const = 0; + }; + + // Provides a cursor into the specific target string. + template<typename _FwdIterT> + class _SpecializedCursor + : public _PatternCursor + { + public: + _SpecializedCursor(const _FwdIterT& __b, const _FwdIterT __e) + : _M_b(__b), _M_c(__b), _M_e(__e) + { } + + typename std::iterator_traits<_FwdIterT>::value_type + _M_current() const + { return *_M_c; } + + void + _M_next() + { ++_M_c; } + + _FwdIterT + _M_pos() const + { return _M_c; } + + const _FwdIterT& + _M_begin() const + { return _M_b; } + + const _FwdIterT& + _M_end() const + { return _M_e; } + + bool + _M_at_end() const + { return _M_c == _M_e; } + + private: + _FwdIterT _M_b; + _FwdIterT _M_c; + _FwdIterT _M_e; + }; + + // Helper funxtion to create a cursor specialized for an iterator class. + template<typename _FwdIterT> + inline _SpecializedCursor<_FwdIterT> + __cursor(const _FwdIterT& __b, const _FwdIterT __e) + { return _SpecializedCursor<_FwdIterT>(__b, __e); } + +} // namespace __regex +} // namespace std + +/* vim: set ts=8 sw=2 sts=2: */ diff --git a/libstdc++-v3/include/bits/regex_error.h b/libstdc++-v3/include/bits/regex_error.h new file mode 100644 index 00000000000..56bfae4cc66 --- /dev/null +++ b/libstdc++-v3/include/bits/regex_error.h @@ -0,0 +1,160 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_error + * @brief Error and exception objects for the std regex library. + * + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ + +namespace regex_constants +{ + /** + * @name 5.3 Error Types + */ + //@{ + + enum error_type + { + _S_error_collate, + _S_error_ctype, + _S_error_escape, + _S_error_backref, + _S_error_brack, + _S_error_paren, + _S_error_brace, + _S_error_badbrace, + _S_error_range, + _S_error_space, + _S_error_badrepeat, + _S_error_complexity, + _S_error_stack, + _S_error_last + }; + + /** The expression contained an invalid collating element name. */ + static const error_type error_collate(_S_error_collate); + + /** The expression contained an invalid character class name. */ + static const error_type error_ctype(_S_error_ctype); + + /** + * The expression contained an invalid escaped character, or a trailing + * escape. + */ + static const error_type error_escape(_S_error_escape); + + /** The expression contained an invalid back reference. */ + static const error_type error_backref(_S_error_backref); + + /** The expression contained mismatched [ and ]. */ + static const error_type error_brack(_S_error_brack); + + /** The expression contained mismatched ( and ). */ + static const error_type error_paren(_S_error_paren); + + /** The expression contained mismatched { and } */ + static const error_type error_brace(_S_error_brace); + + /** The expression contained an invalid range in a {} expression. */ + static const error_type error_badbrace(_S_error_badbrace); + + /** + * The expression contained an invalid character range, + * such as [b-a] in most encodings. + */ + static const error_type error_range(_S_error_range); + + /** + * There was insufficient memory to convert the expression into a + * finite state machine. + */ + static const error_type error_space(_S_error_space); + + /** + * One of <em>*?+{<em> was not preceded by a valid regular expression. + */ + static const error_type error_badrepeat(_S_error_badrepeat); + + /** + * The complexity of an attempted match against a regular expression + * exceeded a pre-set level. + */ + static const error_type error_complexity(_S_error_complexity); + + /** + * There was insufficient memory to determine whether the + * regular expression could match the specified character sequence. + */ + static const error_type error_stack(_S_error_stack); + + //@} +} + + // [7.8] Class regex_error + /** + * @brief A regular expression exception class. + * @ingroup exceptions + * + * The regular expression library throws objects of this class on error. + */ + class regex_error + : public std::runtime_error + { + public: + /** + * @brief Constructs a regex_error object. + * + * @param ecode the regex error code. + */ + explicit + regex_error(regex_constants::error_type __ecode) + : std::runtime_error("regex_error"), _M_code(__ecode) + { } + + /** + * @brief Gets the regex error code. + * + * @returns the regex error code. + */ + regex_constants::error_type + code() const + { return _M_code; } + + protected: + regex_constants::error_type _M_code; + }; + + + inline void + __throw_regex_error(regex_constants::error_type __ecode) + { throw regex_error(__ecode); } + +} // namespace std + diff --git a/libstdc++-v3/include/bits/regex_grep_matcher.h b/libstdc++-v3/include/bits/regex_grep_matcher.h new file mode 100644 index 00000000000..f243c92406b --- /dev/null +++ b/libstdc++-v3/include/bits/regex_grep_matcher.h @@ -0,0 +1,131 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_executor.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + + +namespace std +{ + template<typename _BiIter> + class sub_match; + + template<typename _Bi_iter, typename _Allocator> + class match_results; + +namespace __regex +{ + // A _Results facade specialized for wrapping a templated sub_match. + template<typename _FwdIterT, typename _Alloc> + class _SpecializedResults + : public _Results + { + public: + _SpecializedResults(const _Automaton::_SizeT __size, + const _SpecializedCursor<_FwdIterT>& __cursor, + match_results<_FwdIterT, _Alloc>& __m); + + void + _M_set_pos(int __i, int __j, const _PatternCursor& __pc); + + void + _M_set_matched(int __i, bool __is_matched) + { _M_results.at(__i).matched = __is_matched; } + + private: + match_results<_FwdIterT, _Alloc>& _M_results; + }; + + template<typename _FwdIterT, typename _Alloc> + _SpecializedResults<_FwdIterT, _Alloc>:: + _SpecializedResults(const _Automaton::_SizeT __size, + const _SpecializedCursor<_FwdIterT>& __cursor, + match_results<_FwdIterT, _Alloc>& __m) + : _M_results(__m) + { + typedef typename match_results<_FwdIterT, _Alloc>::size_type size_type; + _M_results.clear(); + std::sub_match<_FwdIterT> __sm; + __sm.matched = false; + size_type __result_count = __size + 2; + for (size_type __i = 0; __i < __result_count; ++__i) + _M_results.push_back(__sm); + _M_results.at(__size+0).first = __cursor._M_begin(); + _M_results.at(__size+0).second = __cursor._M_begin(); + _M_results.at(__size+1).first = __cursor._M_end(); + _M_results.at(__size+1).second = __cursor._M_end(); + } + + template<typename _FwdIterT, typename _Alloc> + void + _SpecializedResults<_FwdIterT, _Alloc>:: + _M_set_pos(int __i, int __j, const _PatternCursor& __pc) + { + typedef const _SpecializedCursor<_FwdIterT>& _CursorT; + _CursorT __c = static_cast<_CursorT>(__pc); + if (__j == 0) + _M_results.at(__i).first = __c._M_pos(); + else + _M_results.at(__i).second = __c._M_pos()+1; + } + + // A stack of states used in evaluating the NFA. + typedef std::stack<_StateIdT, std::vector<_StateIdT> > _StateStack; + + // Executes a regular expression NFA/DFA over a range using a variant of + // the parallel execution algorithm featured in the grep utility, modified + // to use Laurikari tags. + class _Grep_matcher + { + public: + _Grep_matcher(_PatternCursor& __p, + _Results& __r, + const _AutomatonPtr& __automaton, + regex_constants::match_flag_type __flags); + + private: + _StateSet + _M_e_closure(_StateIdT __i); + + _StateSet + _M_e_closure(const _StateSet& __s); + + _StateSet + _M_e_closure(_StateStack& __stack, const _StateSet& __s); + + private: + const std::shared_ptr<_Nfa> _M_nfa; + _PatternCursor& _M_pattern; + _Results& _M_results; + }; + +} // namespace __regex +} // namespace std + +#include <bits/regex_grep_matcher.tcc> + +/* vim: set ts=8 sw=2 sts=2: */ diff --git a/libstdc++-v3/include/bits/regex_grep_matcher.tcc b/libstdc++-v3/include/bits/regex_grep_matcher.tcc new file mode 100644 index 00000000000..17d1e6449dc --- /dev/null +++ b/libstdc++-v3/include/bits/regex_grep_matcher.tcc @@ -0,0 +1,177 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file regex_grep_matcher.cc + */ +#include <regex> + +namespace std +{ + +namespace +{ + + // A stack of states used in evaluating the NFA. + typedef std::stack<std::__regex::_StateIdT, + std::vector<std::__regex::_StateIdT> + > _StateStack; + + // Obtains the next state set given the current state set __s and the current + // input character. + inline std::__regex::_StateSet + __move(const std::__regex::_PatternCursor& __p, + const std::__regex::_Nfa& __nfa, + const std::__regex::_StateSet& __s) + { + std::__regex::_StateSet __m; + for (std::__regex::_StateSet::const_iterator __i = __s.begin(); + __i != __s.end(); ++__i) + { + if (*__i == std::__regex::_S_invalid_state_id) + continue; + + const std::__regex::_State& __state = __nfa[*__i]; + if (__state._M_opcode == std::__regex::_S_opcode_match + && __state._M_matches(__p)) + __m.insert(__state._M_next); + } + return __m; + } + + // returns true if (__s intersect __t) is not empty + inline bool + __includes_some(const std::__regex::_StateSet& __s, + const std::__regex::_StateSet& __t) + { + if (__s.size() > 0 && __t.size() > 0) + { + std::__regex::_StateSet::const_iterator __first = __s.begin(); + std::__regex::_StateSet::const_iterator __second = __t.begin(); + while (__first != __s.end() && __second != __t.end()) + { + if (*__first < *__second) + ++__first; + else if (*__second < *__first) + ++__second; + else + return true; + } + } + return false; + } + + // If an identified state __u is not already in the current state set __e, + // insert it and push it on the current state stack __s. + inline void + __add_visited_state(const std::__regex::_StateIdT __u, + _StateStack& __s, + std::__regex::_StateSet& __e) + { + if (__e.count(__u) == 0) + { + __e.insert(__u); + __s.push(__u); + } + } + +} // anonymous namespace + +namespace __regex +{ + inline _Grep_matcher:: + _Grep_matcher(_PatternCursor& __p, _Results& __r, + const _AutomatonPtr& __nfa, + regex_constants::match_flag_type __flags) + : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r) + { + __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start()); + for (; !_M_pattern._M_at_end(); _M_pattern._M_next()) + __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t)); + + _M_results._M_set_matched(0, + __includes_some(_M_nfa->_M_final_states(), __t)); + } + + // Creates the e-closure set for the initial state __i. + inline _StateSet _Grep_matcher:: + _M_e_closure(_StateIdT __i) + { + _StateSet __s; + __s.insert(__i); + _StateStack __stack; + __stack.push(__i); + return this->_M_e_closure(__stack, __s); + } + + // Creates the e-closure set for an arbitrary state set __s. + inline _StateSet _Grep_matcher:: + _M_e_closure(const _StateSet& __s) + { + _StateStack __stack; + for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i) + __stack.push(*__i); + return this->_M_e_closure(__stack, __s); + } + + inline _StateSet _Grep_matcher:: + _M_e_closure(_StateStack& __stack, const _StateSet& __s) + { + _StateSet __e = __s; + while (!__stack.empty()) + { + _StateIdT __t = __stack.top(); __stack.pop(); + if (__t == _S_invalid_state_id) + continue; + // for each __u with edge from __t to __u labeled e do ... + const _State& __state = _M_nfa->operator[](__t); + switch (__state._M_opcode) + { + case _S_opcode_alternative: + __add_visited_state(__state._M_next, __stack, __e); + __add_visited_state(__state._M_alt, __stack, __e); + break; + case _S_opcode_subexpr_begin: + __add_visited_state(__state._M_next, __stack, __e); + __state._M_tagger(_M_pattern, _M_results); + break; + case _S_opcode_subexpr_end: + __add_visited_state(__state._M_next, __stack, __e); + __state._M_tagger(_M_pattern, _M_results); + _M_results._M_set_matched(__state._M_subexpr, true); + break; + case _S_opcode_accept: + __add_visited_state(__state._M_next, __stack, __e); + break; + default: + break; + } + } + return __e; + } + +} // namespace __regex +} // namespace std + +/* vim: set ts=8 sw=2 sts=2: */ diff --git a/libstdc++-v3/include/bits/regex_nfa.h b/libstdc++-v3/include/bits/regex_nfa.h new file mode 100644 index 00000000000..2a938915b97 --- /dev/null +++ b/libstdc++-v3/include/bits/regex_nfa.h @@ -0,0 +1,403 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file bits/regex_nfa.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +namespace std +{ +namespace __regex +{ + + // Base class for, um, automata. Could be an NFA or a DFA. Your choice. + class _Automaton + { + public: + typedef unsigned int _SizeT; + + public: + virtual + ~_Automaton() + { } + + virtual _SizeT + _M_sub_count() const = 0; + +#ifdef _GLIBCXX_DEBUG + virtual std::ostream& + _M_dot(std::ostream& __ostr) const = 0; +#endif + }; + + // Generic shred pointer to an automaton. + typedef std::shared_ptr<_Automaton> _AutomatonPtr; + + // Operation codes that define the type of transitions within the base NFA + // that represents the regular expression. + enum _Opcode + { + _S_opcode_unknown = 0, + _S_opcode_alternative = 1, + _S_opcode_subexpr_begin = 4, + _S_opcode_subexpr_end = 5, + _S_opcode_match = 100, + _S_opcode_accept = 255 + }; + + // Provides a generic facade for a templated match_results. + struct _Results + { + virtual void _M_set_pos(int __i, int __j, const _PatternCursor& __p) = 0; + virtual void _M_set_matched(int __i, bool __is_matched) = 0; + }; + + // Tags current state (for subexpr begin/end). + typedef std::function<void (const _PatternCursor&, _Results&)> _Tagger; + + template<typename _FwdIterT, typename _TraitsT> + struct _StartTagger + : public _Tagger + { + explicit + _StartTagger(int __i) + : _M_index(__i) + { } + + void + operator()(const _PatternCursor& __pc, _Results& __r) + { __r._M_set_pos(_M_index, 0, __pc); } + + int _M_index; + }; + + template<typename _FwdIterT, typename _TraitsT> + struct _EndTagger + : public _Tagger + { + explicit + _EndTagger(int __i) + : _M_index(__i) + { } + + void + operator()(const _PatternCursor& __pc, _Results& __r) + { __r._M_set_pos(_M_index, 1, __pc); } + + int _M_index; + _FwdIterT _M_pos; + }; + // Indicates if current state matches cursor current. + typedef std::function<bool (const _PatternCursor&)> _Matcher; + + // Matches any character + inline bool + _AnyMatcher(const _PatternCursor&) + { return true; } + + // Matches a single character + template<typename _InIterT, typename _TraitsT> + struct _CharMatcher + : public _Matcher + { + typedef typename _TraitsT::char_type char_type; + + explicit + _CharMatcher(char_type __c, const _TraitsT& __t = _TraitsT()) + : _M_traits(__t), _M_c(_M_traits.translate(__c)) + { } + + bool + operator()(const _PatternCursor& __pc) const + { + typedef const _SpecializedCursor<_InIterT>& _CursorT; + _CursorT __c = static_cast<_CursorT>(__pc); + return _M_traits.translate(__c._M_current()) == _M_c; + } + + const _TraitsT& _M_traits; + char_type _M_c; + }; + + // Matches a character range (bracket expression) + template<typename _InIterT, typename _TraitsT> + struct _RangeMatcher + : public _Matcher + { + typedef typename _TraitsT::char_type _CharT; + typedef std::basic_string<_CharT> _StringT; + + explicit + _RangeMatcher(bool __is_non_matching, const _TraitsT& __t = _TraitsT()) + : _M_traits(__t), _M_is_non_matching(__is_non_matching) + { } + + bool + operator()(const _PatternCursor& __pc) const + { + typedef const _SpecializedCursor<_InIterT>& _CursorT; + _CursorT __c = static_cast<_CursorT>(__pc); + return true; + } + + void + _M_add_char(_CharT __c) + { } + + void + _M_add_collating_element(const _StringT& __s) + { } + + void + _M_add_equivalence_class(const _StringT& __s) + { } + + void + _M_add_character_class(const _StringT& __s) + { } + + void + _M_make_range() + { } + + const _TraitsT& _M_traits; + bool _M_is_non_matching; + }; + + // Identifies a state in the NFA. + typedef int _StateIdT; + + // The special case in which a state identifier is not an index. + static const _StateIdT _S_invalid_state_id = -1; + + + // An individual state in an NFA + // + // In this case a "state" is an entry in the NFA definition coupled with its + // outgoing transition(s). All states have a single outgoing transition, + // except for accepting states (which have no outgoing transitions) and alt + // states, which have two outgoing transitions. + // + struct _State + { + typedef int _OpcodeT; + + _OpcodeT _M_opcode; // type of outgoing transition + _StateIdT _M_next; // outgoing tranition + _StateIdT _M_alt; // for _S_opcode_alternative + unsigned int _M_subexpr; // for _S_opcode_subexpr_* + _Tagger _M_tagger; // for _S_opcode_subexpr_* + _Matcher _M_matches; // for _S_opcode_match + + explicit _State(_OpcodeT __opcode) + : _M_opcode(__opcode), _M_next(_S_invalid_state_id) + { } + + _State(const _Matcher& __m) + : _M_opcode(_S_opcode_match), _M_next(_S_invalid_state_id), _M_matches(__m) + { } + + _State(_OpcodeT __opcode, unsigned int __s, const _Tagger& __t) + : _M_opcode(__opcode), _M_next(_S_invalid_state_id), _M_subexpr(__s), + _M_tagger(__t) + { } + + _State(_StateIdT __next, _StateIdT __alt) + : _M_opcode(_S_opcode_alternative), _M_next(__next), _M_alt(__alt) + { } + +#ifdef _GLIBCXX_DEBUG + std::ostream& + _M_print(std::ostream& ostr) const; + + // Prints graphviz dot commands for state. + std::ostream& + _M_dot(std::ostream& __ostr, _StateIdT __id) const; +#endif + }; + + + // The Grep Matcher works on sets of states. Here are sets of states. + typedef std::set<_StateIdT> _StateSet; + + // A collection of all states making up an NFA + // + // An NFA is a 4-tuple M = (K, S, s, F), where + // K is a finite set of states, + // S is the alphabet of the NFA, + // s is the initial state, + // F is a set of final (accepting) states. + // + // This NFA class is templated on S, a type that will hold values of the + // underlying alphabet (without regard to semantics of that alphabet). The + // other elements of the tuple are generated during construction of the NFA + // and are available through accessor member functions. + // + class _Nfa + : public _Automaton, public std::vector<_State> + { + public: + typedef _State _StateT; + typedef unsigned int _SizeT; + typedef regex_constants::syntax_option_type _FlagT; + + public: + _Nfa(_FlagT __f) + : _M_flags(__f), _M_start_state(0), _M_subexpr_count(0) + { } + + ~_Nfa() + { } + + _FlagT + _M_options() const + { return _M_flags; } + + _StateIdT + _M_start() const + { return _M_start_state; } + + const _StateSet& + _M_final_states() const + { return _M_accepting_states; } + + _SizeT + _M_sub_count() const + { return _M_subexpr_count; } + + _StateIdT + _M_insert_accept() + { + this->push_back(_StateT(_S_opcode_accept)); + _M_accepting_states.insert(this->size()-1); + return this->size()-1; + } + + _StateIdT + _M_insert_alt(_StateIdT __next, _StateIdT __alt) + { + this->push_back(_StateT(__next, __alt)); + return this->size()-1; + } + + _StateIdT + _M_insert_matcher(_Matcher __m) + { + this->push_back(_StateT(__m)); + return this->size()-1; + } + + _StateIdT + _M_insert_subexpr_begin(const _Tagger& __t) + { + this->push_back(_StateT(_S_opcode_subexpr_begin, _M_subexpr_count++, __t)); + return this->size()-1; + } + + _StateIdT + _M_insert_subexpr_end(unsigned int __i, const _Tagger& __t) + { + this->push_back(_StateT(_S_opcode_subexpr_end, __i, __t)); + return this->size()-1; + } + +#ifdef _GLIBCXX_DEBUG + std::ostream& + _M_dot(std::ostream& __ostr) const; +#endif + + private: + _FlagT _M_flags; + _StateIdT _M_start_state; + _StateSet _M_accepting_states; + _SizeT _M_subexpr_count; + }; + + // Describes a sequence of one or more %_State, its current start and end(s). + // + // This structure contains fragments of an NFA during construction. + class _StateSeq + { + public: + // Constructs a single-node sequence + _StateSeq(_Nfa& __ss, _StateIdT __s, _StateIdT __e = _S_invalid_state_id) + : _M_nfa(__ss), _M_start(__s), _M_end1(__s), _M_end2(__e) + { } + // Constructs a split sequence from two other sequencces + _StateSeq(const _StateSeq& __e1, const _StateSeq& __e2) + : _M_nfa(__e1._M_nfa), + _M_start(_M_nfa._M_insert_alt(__e1._M_start, __e2._M_start)), + _M_end1(__e1._M_end1), _M_end2(__e2._M_end1) + { } + + // Constructs a split sequence from a single sequence + _StateSeq(const _StateSeq& __e, _StateIdT __id) + : _M_nfa(__e._M_nfa), + _M_start(_M_nfa._M_insert_alt(__id, __e._M_start)), + _M_end1(__id), _M_end2(__e._M_end1) + { } + + // Constructs a copy of a %_StateSeq + _StateSeq(const _StateSeq& __rhs) + : _M_nfa(__rhs._M_nfa), _M_start(__rhs._M_start), + _M_end1(__rhs._M_end1), _M_end2(__rhs._M_end2) + { } + + + _StateSeq& operator=(const _StateSeq& __rhs); + + _StateIdT + _M_front() const + { return _M_start; } + + // Extends a sequence by one. + void + _M_push_back(_StateIdT __id); + + // Extends and maybe joins a sequence. + void + _M_append(_StateIdT __id); + + void + _M_append(_StateSeq& __rhs); + + // Clones an entire sequence. + _StateIdT + _M_clone(); + + private: + _Nfa& _M_nfa; + _StateIdT _M_start; + _StateIdT _M_end1; + _StateIdT _M_end2; + + }; + +} // namespace __regex +} // namespace std + +#include <bits/regex_nfa.tcc> + diff --git a/libstdc++-v3/include/bits/regex_nfa.tcc b/libstdc++-v3/include/bits/regex_nfa.tcc new file mode 100644 index 00000000000..38ab7e0b2ae --- /dev/null +++ b/libstdc++-v3/include/bits/regex_nfa.tcc @@ -0,0 +1,170 @@ +// class template regex -*- C++ -*- + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** + * @file regex_nfa.cc + */ +#include <regex> + +namespace std +{ +namespace __regex +{ +#ifdef _GLIBCXX_DEBUG +inline std::ostream& _State:: +_M_print(std::ostream& ostr) const +{ + switch (_M_opcode) + { + case _S_opcode_alternative: + ostr << "alt next=" << _M_next << " alt=" << _M_alt; + break; + case _S_opcode_subexpr_begin: + ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr; + break; + case _S_opcode_subexpr_end: + ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr; + break; + case _S_opcode_match: + ostr << "match next=" << _M_next; + break; + case _S_opcode_accept: + ostr << "accept next=" << _M_next; + break; + default: + ostr << "unknown next=" << _M_next; + break; + } + return ostr; +} + +// Prints graphviz dot commands for state. +inline std::ostream& _State:: +_M_dot(std::ostream& __ostr, _StateIdT __id) const +{ + switch (_M_opcode) + { + case _S_opcode_alternative: + __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n" + << __id << " -> " << _M_next + << " [label=\"epsilon\", tailport=\"s\"];\n" + << __id << " -> " << _M_alt + << " [label=\"epsilon\", tailport=\"n\"];\n"; + break; + case _S_opcode_subexpr_begin: + __ostr << __id << " [label=\"" << __id << "\\nSBEGIN " + << _M_subexpr << "\"];\n" + << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; + break; + case _S_opcode_subexpr_end: + __ostr << __id << " [label=\"" << __id << "\\nSEND " + << _M_subexpr << "\"];\n" + << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; + break; + case _S_opcode_match: + __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n" + << __id << " -> " << _M_next << " [label=\"<match>\"];\n"; + break; + case _S_opcode_accept: + __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ; + break; + default: + __ostr << __id << " [label=\"" << __id << "\\nUNK\"];\n" + << __id << " -> " << _M_next << " [label=\"?\"];\n"; + break; + } + return __ostr; +} + +inline std::ostream& _Nfa:: +_M_dot(std::ostream& __ostr) const +{ + __ostr << "digraph _Nfa {\n" + << " rankdir=LR;\n"; + for (unsigned int __i = 0; __i < this->size(); ++__i) + { this->at(__i)._M_dot(__ostr, __i); } + __ostr << "}\n"; + return __ostr; +} +#endif + +inline _StateSeq& _StateSeq:: +operator=(const _StateSeq& __rhs) +{ + _M_start = __rhs._M_start; + _M_end1 = __rhs._M_end1; + _M_end2 = __rhs._M_end2; + return *this; +} + +inline void _StateSeq:: +_M_push_back(_StateIdT __id) +{ + if (_M_end1 != _S_invalid_state_id) + _M_nfa[_M_end1]._M_next = __id; + _M_end1 = __id; +} + +inline void _StateSeq:: +_M_append(_StateIdT __id) +{ + if (_M_end2 != _S_invalid_state_id) + { + if (_M_end2 == _M_end1) + _M_nfa[_M_end2]._M_alt = __id; + else + _M_nfa[_M_end2]._M_next = __id; + _M_end2 = _S_invalid_state_id; + } + if (_M_end1 != _S_invalid_state_id) + _M_nfa[_M_end1]._M_next = __id; + _M_end1 = __id; +} + +inline void _StateSeq:: +_M_append(_StateSeq& __rhs) +{ + if (_M_end2 != _S_invalid_state_id) + { + if (_M_end2 == _M_end1) + _M_nfa[_M_end2]._M_alt = __rhs._M_start; + else + _M_nfa[_M_end2]._M_next = __rhs._M_start; + _M_end2 = _S_invalid_state_id; + } + if (__rhs._M_end2 != _S_invalid_state_id) + _M_end2 = __rhs._M_end2; + if (_M_end1 != _S_invalid_state_id) + _M_nfa[_M_end1]._M_next = __rhs._M_start; + _M_end1 = __rhs._M_end1; +} + +// @todo implement this function. +inline _StateIdT _StateSeq:: +_M_clone() +{ return 0; } + +} // namespace __regex +} // namespace std + diff --git a/libstdc++-v3/include/bits/shared_ptr.h b/libstdc++-v3/include/bits/shared_ptr.h index 5e1960012c9..4f87dd459cf 100644 --- a/libstdc++-v3/include/bits/shared_ptr.h +++ b/libstdc++-v3/include/bits/shared_ptr.h @@ -123,6 +123,23 @@ _GLIBCXX_BEGIN_NAMESPACE(std) shared_ptr(_Tp1* __p, _Deleter __d) : __shared_ptr<_Tp>(__p, __d) { } /** + * @brief Construct a %shared_ptr that owns a null pointer + * and the deleter @a __d. + * @param __p A null pointer constant. + * @param __d A deleter. + * @post use_count() == 1 && get() == __p + * @throw std::bad_alloc, in which case @a __d(__p) is called. + * + * Requirements: _Deleter's copy constructor and destructor must + * not throw + * + * The last owner will call __d(__p) + */ + template<typename _Deleter> + shared_ptr(nullptr_t __p, _Deleter __d) + : __shared_ptr<_Tp>(__p, __d) { } + + /** * @brief Construct a %shared_ptr that owns the pointer @a __p * and the deleter @a __d. * @param __p A pointer. @@ -141,6 +158,25 @@ _GLIBCXX_BEGIN_NAMESPACE(std) shared_ptr(_Tp1* __p, _Deleter __d, const _Alloc& __a) : __shared_ptr<_Tp>(__p, __d, __a) { } + /** + * @brief Construct a %shared_ptr that owns a null pointer + * and the deleter @a __d. + * @param __p A null pointer constant. + * @param __d A deleter. + * @param __a An allocator. + * @post use_count() == 1 && get() == __p + * @throw std::bad_alloc, in which case @a __d(__p) is called. + * + * Requirements: _Deleter's copy constructor and destructor must + * not throw _Alloc's copy constructor and destructor must not + * throw. + * + * The last owner will call __d(__p) + */ + template<typename _Deleter, typename _Alloc> + shared_ptr(nullptr_t __p, _Deleter __d, const _Alloc& __a) + : __shared_ptr<_Tp>(__p, __d, __a) { } + // Aliasing constructor /** @@ -212,6 +248,13 @@ _GLIBCXX_BEGIN_NAMESPACE(std) shared_ptr(std::unique_ptr<_Tp1, _Del>&& __r) : __shared_ptr<_Tp>(std::move(__r)) { } + /** + * @brief Construct an empty %shared_ptr. + * @param __p A null pointer constant. + * @post use_count() == 0 && get() == nullptr + */ + shared_ptr(nullptr_t __p) : __shared_ptr<_Tp>(__p) { } + template<typename _Tp1> shared_ptr& operator=(const shared_ptr<_Tp1>& __r) // never throws @@ -471,6 +514,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::forward<_Args>(__args)...); } + /// std::hash specialization for shared_ptr. + template<typename _Tp> + struct hash<shared_ptr<_Tp>> + : public std::unary_function<shared_ptr<_Tp>, size_t> + { + size_t + operator()(const shared_ptr<_Tp>& __s) const + { return std::hash<_Tp*>()(__s.get()); } + }; + // @} group pointer_abstractions _GLIBCXX_END_NAMESPACE diff --git a/libstdc++-v3/include/bits/shared_ptr_base.h b/libstdc++-v3/include/bits/shared_ptr_base.h index 0c366b8ef1a..0a69d2b2411 100644 --- a/libstdc++-v3/include/bits/shared_ptr_base.h +++ b/libstdc++-v3/include/bits/shared_ptr_base.h @@ -85,6 +85,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) class _Sp_counted_ptr : public _Sp_counted_base<_Lp> { public: + explicit _Sp_counted_ptr(_Ptr __p) : _M_ptr(__p) { } @@ -107,6 +108,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Ptr _M_ptr; // copy constructor must not throw }; + template<> + inline void + _Sp_counted_ptr<nullptr_t, _S_single>::_M_dispose() { } + + template<> + inline void + _Sp_counted_ptr<nullptr_t, _S_mutex>::_M_dispose() { } + + template<> + inline void + _Sp_counted_ptr<nullptr_t, _S_atomic>::_M_dispose() { } + // Support for custom deleter and/or allocator template<typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp> class _Sp_counted_deleter : public _Sp_counted_ptr<_Ptr, _Lp> @@ -181,6 +194,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Base_type; public: + explicit _Sp_counted_ptr_inplace(_Alloc __a) : _Base_type(static_cast<_Tp*>(0), _Sp_destroy_inplace<_Tp>(), __a) , _M_storage() @@ -237,6 +251,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { } template<typename _Ptr> + explicit __shared_count(_Ptr __p) : _M_pi(0) { __try @@ -316,6 +331,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) #if _GLIBCXX_DEPRECATED // Special case for auto_ptr<_Tp> to provide the strong guarantee. template<typename _Tp> + explicit __shared_count(std::auto_ptr<_Tp>&& __r) : _M_pi(new _Sp_counted_ptr<_Tp*, _Lp>(__r.get())) { __r.release(); } @@ -323,6 +339,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // Special case for unique_ptr<_Tp,_Del> to provide the strong guarantee. template<typename _Tp, typename _Del> + explicit __shared_count(std::unique_ptr<_Tp, _Del>&& __r) : _M_pi(_S_create_from_up(std::move(__r))) { __r.release(); } @@ -567,6 +584,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __enable_shared_from_this_helper(_M_refcount, __p, __p); } + template<typename _Deleter> + __shared_ptr(nullptr_t __p, _Deleter __d) + : _M_ptr(0), _M_refcount(__p, __d) + { } + + template<typename _Deleter, typename _Alloc> + __shared_ptr(nullptr_t __p, _Deleter __d, const _Alloc& __a) + : _M_ptr(0), _M_refcount(__p, __d, __a) + { } + template<typename _Tp1> __shared_ptr(const __shared_ptr<_Tp1, _Lp>& __r, _Tp* __p) : _M_ptr(__p), _M_refcount(__r._M_refcount) // never throws @@ -631,6 +658,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } #endif + /* TODO: use delegating constructor */ + __shared_ptr(nullptr_t) : _M_ptr(0), _M_refcount() // never throws + { } + template<typename _Tp1> __shared_ptr& operator=(const __shared_ptr<_Tp1, _Lp>& __r) // never throws @@ -1133,6 +1164,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::forward<_Args>(__args)...); } + /// std::hash specialization for __shared_ptr. + template<typename _Tp, _Lock_policy _Lp> + struct hash<__shared_ptr<_Tp, _Lp>> + : public std::unary_function<__shared_ptr<_Tp, _Lp>, size_t> + { + size_t + operator()(const __shared_ptr<_Tp, _Lp>& __s) const + { return std::hash<_Tp*>()(__s.get()); } + }; + _GLIBCXX_END_NAMESPACE #endif // _SHARED_PTR_BASE_H diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 0489c413b95..cfaeef8f645 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -58,7 +58,6 @@ #define _STL_ALGOBASE_H 1 #include <bits/c++config.h> -#include <cstddef> #include <bits/functexcept.h> #include <bits/cpp_type_traits.h> #include <ext/type_traits.h> @@ -395,7 +394,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_II>::value_type _ValueTypeI; typedef typename iterator_traits<_OI>::value_type _ValueTypeO; typedef typename iterator_traits<_II>::iterator_category _Category; - const bool __simple = (__is_pod(_ValueTypeI) + const bool __simple = (__is_trivial(_ValueTypeI) && __is_pointer<_II>::__value && __is_pointer<_OI>::__value && __are_same<_ValueTypeI, _ValueTypeO>::__value); @@ -590,7 +589,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_BI1>::value_type _ValueType1; typedef typename iterator_traits<_BI2>::value_type _ValueType2; typedef typename iterator_traits<_BI1>::iterator_category _Category; - const bool __simple = (__is_pod(_ValueType1) + const bool __simple = (__is_trivial(_ValueType1) && __is_pointer<_BI1>::__value && __is_pointer<_BI2>::__value && __are_same<_ValueType1, _ValueType2>::__value); diff --git a/libstdc++-v3/include/bits/stl_construct.h b/libstdc++-v3/include/bits/stl_construct.h index 06a2902ca69..d84b8f164fd 100644 --- a/libstdc++-v3/include/bits/stl_construct.h +++ b/libstdc++-v3/include/bits/stl_construct.h @@ -67,19 +67,21 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * Constructs an object in existing memory by invoking an allocated * object's constructor with an initializer. */ - template<typename _T1, typename _T2> - inline void #ifdef __GXX_EXPERIMENTAL_CXX0X__ - // Allow perfect forwarding - _Construct(_T1* __p, _T2&& __value) + template<typename _T1, typename... _Args> + inline void + _Construct(_T1* __p, _Args&&... __args) + { ::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...); } #else + template<typename _T1, typename _T2> + inline void _Construct(_T1* __p, const _T2& __value) -#endif { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 402. wrong new expression in [some_]allocator::construct - ::new(static_cast<void*>(__p)) _T1(_GLIBCXX_FORWARD(_T2, __value)); + ::new(static_cast<void*>(__p)) _T1(__value); } +#endif /** * Destroy the object pointed to by a pointer type. diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 19022b0cf34..d3cd73997e9 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -449,6 +449,10 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) : _M_impl() { _M_initialize_map(0); } + _Deque_base(size_t __num_elements) + : _M_impl() + { _M_initialize_map(__num_elements); } + _Deque_base(const allocator_type& __a, size_t __num_elements) : _M_impl(__a) { _M_initialize_map(__num_elements); } @@ -773,6 +777,32 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) deque(const allocator_type& __a) : _Base(__a, 0) { } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Creates a %deque with default constructed elements. + * @param n The number of elements to initially create. + * + * This constructor fills the %deque with @a n default + * constructed elements. + */ + explicit + deque(size_type __n) + : _Base(__n) + { _M_default_initialize(); } + + /** + * @brief Creates a %deque with copies of an exemplar element. + * @param n The number of elements to initially create. + * @param value An element to copy. + * @param a An allocator. + * + * This constructor fills the %deque with @a n copies of @a value. + */ + deque(size_type __n, const value_type& __value, + const allocator_type& __a = allocator_type()) + : _Base(__a, __n) + { _M_fill_initialize(__value); } +#else /** * @brief Creates a %deque with copies of an exemplar element. * @param n The number of elements to initially create. @@ -786,6 +816,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) const allocator_type& __a = allocator_type()) : _Base(__a, __n) { _M_fill_initialize(__value); } +#endif /** * @brief %Deque copy constructor. @@ -824,11 +855,11 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) */ deque(initializer_list<value_type> __l, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_range_initialize(__l.begin(), __l.end(), - random_access_iterator_tag()); - } + : _Base(__a) + { + _M_range_initialize(__l.begin(), __l.end(), + random_access_iterator_tag()); + } #endif /** @@ -1086,6 +1117,49 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) max_size() const { return _M_get_Tp_allocator().max_size(); } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Resizes the %deque to the specified number of elements. + * @param new_size Number of elements the %deque should contain. + * + * This function will %resize the %deque to the specified + * number of elements. If the number is smaller than the + * %deque's current size the %deque is truncated, otherwise + * default constructed elements are appended. + */ + void + resize(size_type __new_size) + { + const size_type __len = size(); + if (__new_size > __len) + _M_default_append(__new_size - __len); + else if (__new_size < __len) + _M_erase_at_end(this->_M_impl._M_start + + difference_type(__new_size)); + } + + /** + * @brief Resizes the %deque to the specified number of elements. + * @param new_size Number of elements the %deque should contain. + * @param x Data with which new elements should be populated. + * + * This function will %resize the %deque to the specified + * number of elements. If the number is smaller than the + * %deque's current size the %deque is truncated, otherwise the + * %deque is extended and new elements are populated with given + * data. + */ + void + resize(size_type __new_size, const value_type& __x) + { + const size_type __len = size(); + if (__new_size > __len) + insert(this->_M_impl._M_finish, __new_size - __len, __x); + else if (__new_size < __len) + _M_erase_at_end(this->_M_impl._M_start + + difference_type(__new_size)); + } +#else /** * @brief Resizes the %deque to the specified number of elements. * @param new_size Number of elements the %deque should contain. @@ -1101,11 +1175,13 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) resize(size_type __new_size, value_type __x = value_type()) { const size_type __len = size(); - if (__new_size < __len) - _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size)); - else + if (__new_size > __len) insert(this->_M_impl._M_finish, __new_size - __len, __x); + else if (__new_size < __len) + _M_erase_at_end(this->_M_impl._M_start + + difference_type(__new_size)); } +#endif #ifdef __GXX_EXPERIMENTAL_CXX0X__ /** A non-binding request to reduce memory use. */ @@ -1564,6 +1640,12 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) void _M_fill_initialize(const value_type& __value); +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + // called by deque(n). + void + _M_default_initialize(); +#endif + // Internal assign functions follow. The *_aux functions do the actual // assignment work for the range versions. @@ -1752,6 +1834,12 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) this->_M_impl._M_finish = __pos; } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + // Called by resize(sz). + void + _M_default_append(size_type __n); +#endif + //@{ /// Memory-handling helpers for the previous internal insert functions. iterator diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h index 07687bd2cd3..d934f434e6d 100644 --- a/libstdc++-v3/include/bits/stl_iterator_base_types.h +++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h @@ -63,7 +63,6 @@ #pragma GCC system_header #include <bits/c++config.h> -#include <cstddef> _GLIBCXX_BEGIN_NAMESPACE(std) diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 56357ed07da..d6f9255752f 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -508,6 +508,32 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) list(const allocator_type& __a) : _Base(__a) { } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Creates a %list with default constructed elements. + * @param n The number of elements to initially create. + * + * This constructor fills the %list with @a n default + * constructed elements. + */ + explicit + list(size_type __n) + : _Base() + { _M_default_initialize(__n); } + + /** + * @brief Creates a %list with copies of an exemplar element. + * @param n The number of elements to initially create. + * @param value An element to copy. + * @param a An allocator object. + * + * This constructor fills the %list with @a n copies of @a value. + */ + list(size_type __n, const value_type& __value, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { _M_fill_initialize(__n, __value); } +#else /** * @brief Creates a %list with copies of an exemplar element. * @param n The number of elements to initially create. @@ -521,6 +547,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) const allocator_type& __a = allocator_type()) : _Base(__a) { _M_fill_initialize(__n, __value); } +#endif /** * @brief %List copy constructor. @@ -811,6 +838,32 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) max_size() const { return _M_get_Node_allocator().max_size(); } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Resizes the %list to the specified number of elements. + * @param new_size Number of elements the %list should contain. + * + * This function will %resize the %list to the specified number + * of elements. If the number is smaller than the %list's + * current size the %list is truncated, otherwise default + * constructed elements are appended. + */ + void + resize(size_type __new_size); + + /** + * @brief Resizes the %list to the specified number of elements. + * @param new_size Number of elements the %list should contain. + * @param x Data with which new elements should be populated. + * + * This function will %resize the %list to the specified number + * of elements. If the number is smaller than the %list's + * current size the %list is truncated, otherwise the %list is + * extended and new elements are populated with given data. + */ + void + resize(size_type __new_size, const value_type& __x); +#else /** * @brief Resizes the %list to the specified number of elements. * @param new_size Number of elements the %list should contain. @@ -823,6 +876,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) */ void resize(size_type __new_size, value_type __x = value_type()); +#endif // element access /** @@ -1394,10 +1448,23 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) void _M_fill_initialize(size_type __n, const value_type& __x) { - for (; __n > 0; --__n) + for (; __n; --__n) push_back(__x); } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + // Called by list(n). + void + _M_default_initialize(size_type __n) + { + for (; __n; --__n) + emplace_back(); + } + + // Called by resize(sz). + void + _M_default_append(size_type __n); +#endif // Internal assign functions follow. diff --git a/libstdc++-v3/include/bits/stl_pair.h b/libstdc++-v3/include/bits/stl_pair.h index 6c2b51e4c6b..c5f2986fb77 100644 --- a/libstdc++-v3/include/bits/stl_pair.h +++ b/libstdc++-v3/include/bits/stl_pair.h @@ -120,10 +120,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } - pair(pair&& __p) - : first(std::move(__p.first)), - second(std::move(__p.second)) { } - template<class... _Args1, class... _Args2> pair(piecewise_construct_t, tuple<_Args1...> __first_args, @@ -141,8 +137,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) #ifdef __GXX_EXPERIMENTAL_CXX0X__ template<class _U1, class _U2> pair(pair<_U1, _U2>&& __p) - : first(std::move(__p.first)), - second(std::move(__p.second)) { } + : first(std::forward<_U1>(__p.first)), + second(std::forward<_U2>(__p.second)) { } pair& operator=(pair&& __p) diff --git a/libstdc++-v3/include/bits/stl_tempbuf.h b/libstdc++-v3/include/bits/stl_tempbuf.h index a08b1ee1324..47571179c87 100644 --- a/libstdc++-v3/include/bits/stl_tempbuf.h +++ b/libstdc++-v3/include/bits/stl_tempbuf.h @@ -59,7 +59,6 @@ #include <bits/stl_algobase.h> #include <bits/stl_construct.h> -#include <bits/stl_uninitialized.h> _GLIBCXX_BEGIN_NAMESPACE(std) @@ -176,6 +175,70 @@ _GLIBCXX_BEGIN_NAMESPACE(std) operator=(const _Temporary_buffer&); }; + + template<bool> + struct __uninitialized_construct_buf_dispatch + { + template<typename _ForwardIterator, typename _Tp> + static void + __ucr(_ForwardIterator __first, _ForwardIterator __last, + _Tp& __value) + { + if(__first == __last) + return; + + _ForwardIterator __cur = __first; + __try + { + std::_Construct(std::__addressof(*__first), + _GLIBCXX_MOVE(__value)); + _ForwardIterator __prev = __cur; + ++__cur; + for(; __cur != __last; ++__cur, ++__prev) + std::_Construct(std::__addressof(*__cur), + _GLIBCXX_MOVE(*__prev)); + __value = _GLIBCXX_MOVE(*__prev); + } + __catch(...) + { + std::_Destroy(__first, __cur); + __throw_exception_again; + } + } + }; + + template<> + struct __uninitialized_construct_buf_dispatch<true> + { + template<typename _ForwardIterator, typename _Tp> + static void + __ucr(_ForwardIterator, _ForwardIterator, _Tp&) { } + }; + + // Constructs objects in the range [first, last). + // Note that while these new objects will take valid values, + // their exact value is not defined. In particular they may + // be 'moved from'. + // + // While __value may altered during this algorithm, it will have + // the same value when the algorithm finishes, unless one of the + // constructions throws. + // + // Requirements: _ForwardIterator::value_type(_Tp&&) is valid. + template<typename _ForwardIterator, typename _Tp> + inline void + __uninitialized_construct_buf(_ForwardIterator __first, + _ForwardIterator __last, + _Tp& __value) + { + typedef typename std::iterator_traits<_ForwardIterator>::value_type + _ValueType; + + std::__uninitialized_construct_buf_dispatch< + __has_trivial_constructor(_ValueType)>:: + __ucr(__first, __last, __value); + } + template<typename _ForwardIterator, typename _Tp> _Temporary_buffer<_ForwardIterator, _Tp>:: _Temporary_buffer(_ForwardIterator __first, _ForwardIterator __last) @@ -189,8 +252,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _M_buffer = __p.first; _M_len = __p.second; if(_M_buffer) - std::__uninitialized_construct_range(_M_buffer, _M_buffer + _M_len, - *__first); + std::__uninitialized_construct_buf(_M_buffer, _M_buffer + _M_len, + *__first); } __catch(...) { diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 58c63cf4376..4e9fdf73b55 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1358,7 +1358,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // DR 130. Associative erase should return an iterator. template<typename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc> - inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: erase(iterator __position) { @@ -1377,7 +1377,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // DR 130. Associative erase should return an iterator. template<typename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc> - inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: erase(const_iterator __position) { diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h index b78f92025c3..c5cbde0c1a4 100644 --- a/libstdc++-v3/include/bits/stl_uninitialized.h +++ b/libstdc++-v3/include/bits/stl_uninitialized.h @@ -60,13 +60,13 @@ _GLIBCXX_BEGIN_NAMESPACE(std) - template<bool> + template<bool _TrivialValueTypes> struct __uninitialized_copy { template<typename _InputIterator, typename _ForwardIterator> static _ForwardIterator - uninitialized_copy(_InputIterator __first, _InputIterator __last, - _ForwardIterator __result) + __uninit_copy(_InputIterator __first, _InputIterator __last, + _ForwardIterator __result) { _ForwardIterator __cur = __result; __try @@ -88,8 +88,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { template<typename _InputIterator, typename _ForwardIterator> static _ForwardIterator - uninitialized_copy(_InputIterator __first, _InputIterator __last, - _ForwardIterator __result) + __uninit_copy(_InputIterator __first, _InputIterator __last, + _ForwardIterator __result) { return std::copy(__first, __last, __result); } }; @@ -112,19 +112,19 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2; - return std::__uninitialized_copy<(__is_pod(_ValueType1) - && __is_pod(_ValueType2))>:: - uninitialized_copy(__first, __last, __result); + return std::__uninitialized_copy<(__is_trivial(_ValueType1) + && __is_trivial(_ValueType2))>:: + __uninit_copy(__first, __last, __result); } - template<bool> + template<bool _TrivialValueType> struct __uninitialized_fill { template<typename _ForwardIterator, typename _Tp> static void - uninitialized_fill(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __x) + __uninit_fill(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __x) { _ForwardIterator __cur = __first; __try @@ -145,8 +145,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { template<typename _ForwardIterator, typename _Tp> static void - uninitialized_fill(_ForwardIterator __first, - _ForwardIterator __last, const _Tp& __x) + __uninit_fill(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __x) { std::fill(__first, __last, __x); } }; @@ -167,82 +167,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; - std::__uninitialized_fill<__is_pod(_ValueType)>:: - uninitialized_fill(__first, __last, __x); + std::__uninitialized_fill<__is_trivial(_ValueType)>:: + __uninit_fill(__first, __last, __x); } - template<bool> - struct __uninitialized_construct_range_dispatch - { - template<typename _ForwardIterator, typename _Tp> - static void - __ucr(_ForwardIterator __first, _ForwardIterator __last, - _Tp& __value) - { - if(__first == __last) - return; - - _ForwardIterator __cur = __first; - __try - { - std::_Construct(std::__addressof(*__first), - _GLIBCXX_MOVE(__value)); - _ForwardIterator __prev = __cur; - ++__cur; - for(; __cur != __last; ++__cur, ++__prev) - std::_Construct(std::__addressof(*__cur), - _GLIBCXX_MOVE(*__prev)); - __value = _GLIBCXX_MOVE(*__prev); - } - __catch(...) - { - std::_Destroy(__first, __cur); - __throw_exception_again; - } - } - }; - - template<> - struct __uninitialized_construct_range_dispatch<true> - { - template<typename _ForwardIterator, typename _Tp> - static void - __ucr(_ForwardIterator, _ForwardIterator, _Tp&) { } - }; - - // Constructs objects in the range [first, last). - // Note that while these new objects will take valid values, - // their exact value is not defined. In particular they may - // be 'moved from'. - // - // While __value may altered during this algorithm, it will have - // the same value when the algorithm finishes, unless one of the - // constructions throws. - // - // Requirements: _ForwardIterator::value_type(_Tp&&) is valid. - template<typename _ForwardIterator, typename _Tp> - inline void - __uninitialized_construct_range(_ForwardIterator __first, - _ForwardIterator __last, - _Tp& __value) - { - typedef typename std::iterator_traits<_ForwardIterator>::value_type - _ValueType; - - std::__uninitialized_construct_range_dispatch< - __has_trivial_constructor(_ValueType)>:: - __ucr(__first, __last, __value); - } - - - template<bool> + template<bool _TrivialValueType> struct __uninitialized_fill_n { template<typename _ForwardIterator, typename _Size, typename _Tp> static void - uninitialized_fill_n(_ForwardIterator __first, _Size __n, - const _Tp& __x) + __uninit_fill_n(_ForwardIterator __first, _Size __n, + const _Tp& __x) { _ForwardIterator __cur = __first; __try @@ -263,8 +199,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { template<typename _ForwardIterator, typename _Size, typename _Tp> static void - uninitialized_fill_n(_ForwardIterator __first, _Size __n, - const _Tp& __x) + __uninit_fill_n(_ForwardIterator __first, _Size __n, + const _Tp& __x) { std::fill_n(__first, __n, __x); } }; @@ -284,8 +220,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; - std::__uninitialized_fill_n<__is_pod(_ValueType)>:: - uninitialized_fill_n(__first, __n, __x); + std::__uninitialized_fill_n<__is_trivial(_ValueType)>:: + __uninit_fill_n(__first, __n, __x); } // Extensions: versions of uninitialized_copy, uninitialized_fill, @@ -491,6 +427,166 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } #ifdef __GXX_EXPERIMENTAL_CXX0X__ + // Extensions: __uninitialized_default, __uninitialized_default_n, + // __uninitialized_default_a, __uninitialized_default_n_a. + + template<bool _TrivialValueType> + struct __uninitialized_default_1 + { + template<typename _ForwardIterator> + static void + __uninit_default(_ForwardIterator __first, _ForwardIterator __last) + { + _ForwardIterator __cur = __first; + __try + { + for (; __cur != __last; ++__cur) + std::_Construct(std::__addressof(*__cur)); + } + __catch(...) + { + std::_Destroy(__first, __cur); + __throw_exception_again; + } + } + }; + + template<> + struct __uninitialized_default_1<true> + { + template<typename _ForwardIterator> + static void + __uninit_default(_ForwardIterator __first, _ForwardIterator __last) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + + std::fill(__first, __last, _ValueType()); + } + }; + + template<bool _TrivialValueType> + struct __uninitialized_default_n_1 + { + template<typename _ForwardIterator, typename _Size> + static void + __uninit_default_n(_ForwardIterator __first, _Size __n) + { + _ForwardIterator __cur = __first; + __try + { + for (; __n > 0; --__n, ++__cur) + std::_Construct(std::__addressof(*__cur)); + } + __catch(...) + { + std::_Destroy(__first, __cur); + __throw_exception_again; + } + } + }; + + template<> + struct __uninitialized_default_n_1<true> + { + template<typename _ForwardIterator, typename _Size> + static void + __uninit_default_n(_ForwardIterator __first, _Size __n) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + + std::fill_n(__first, __n, _ValueType()); + } + }; + + // __uninitialized_default + // Fills [first, last) with std::distance(first, last) default + // constructed value_types(s). + template<typename _ForwardIterator> + inline void + __uninitialized_default(_ForwardIterator __first, + _ForwardIterator __last) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + + std::__uninitialized_default_1<__is_trivial(_ValueType)>:: + __uninit_default(__first, __last); + } + + // __uninitialized_default_n + // Fills [first, first + n) with n default constructed value_type(s). + template<typename _ForwardIterator, typename _Size> + inline void + __uninitialized_default_n(_ForwardIterator __first, _Size __n) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + + std::__uninitialized_default_n_1<__is_trivial(_ValueType)>:: + __uninit_default_n(__first, __n); + } + + + // __uninitialized_default_a + // Fills [first, last) with std::distance(first, last) default + // constructed value_types(s), constructed with the allocator alloc. + template<typename _ForwardIterator, typename _Allocator> + void + __uninitialized_default_a(_ForwardIterator __first, + _ForwardIterator __last, + _Allocator& __alloc) + { + _ForwardIterator __cur = __first; + __try + { + for (; __cur != __last; ++__cur) + __alloc.construct(std::__addressof(*__cur)); + } + __catch(...) + { + std::_Destroy(__first, __cur, __alloc); + __throw_exception_again; + } + } + + template<typename _ForwardIterator, typename _Tp> + inline void + __uninitialized_default_a(_ForwardIterator __first, + _ForwardIterator __last, + allocator<_Tp>&) + { std::__uninitialized_default(__first, __last); } + + + // __uninitialized_default_n_a + // Fills [first, first + n) with n default constructed value_types(s), + // constructed with the allocator alloc. + template<typename _ForwardIterator, typename _Size, typename _Allocator> + void + __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, + _Allocator& __alloc) + { + _ForwardIterator __cur = __first; + __try + { + for (; __n > 0; --__n, ++__cur) + __alloc.construct(std::__addressof(*__cur)); + } + __catch(...) + { + std::_Destroy(__first, __cur, __alloc); + __throw_exception_again; + } + } + + template<typename _ForwardIterator, typename _Size, typename _Tp> + inline void + __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, + allocator<_Tp>&) + { std::__uninitialized_default_n(__first, __n); } + + template<typename _InputIterator, typename _Size, typename _ForwardIterator> _ForwardIterator @@ -501,8 +597,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __try { for (; __n > 0; --__n, ++__first, ++__cur) - ::new(static_cast<void*>(std::__addressof(*__cur))) typename - iterator_traits<_ForwardIterator>::value_type(*__first); + std::_Construct(std::__addressof(*__cur), *__first); return __cur; } __catch(...) diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index f025b4eeb45..d51578c9e05 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -107,6 +107,14 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) _Vector_base(const allocator_type& __a) : _M_impl(__a) { } + _Vector_base(size_t __n) + : _M_impl() + { + this->_M_impl._M_start = this->_M_allocate(__n); + this->_M_impl._M_finish = this->_M_impl._M_start; + this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; + } + _Vector_base(size_t __n, const allocator_type& __a) : _M_impl(__a) { @@ -215,6 +223,32 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) vector(const allocator_type& __a) : _Base(__a) { } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Creates a %vector with default constructed elements. + * @param n The number of elements to initially create. + * + * This constructor fills the %vector with @a n default + * constructed elements. + */ + explicit + vector(size_type __n) + : _Base(__n) + { _M_default_initialize(__n); } + + /** + * @brief Creates a %vector with copies of an exemplar element. + * @param n The number of elements to initially create. + * @param value An element to copy. + * @param a An allocator. + * + * This constructor fills the %vector with @a n copies of @a value. + */ + vector(size_type __n, const value_type& __value, + const allocator_type& __a = allocator_type()) + : _Base(__n, __a) + { _M_fill_initialize(__n, __value); } +#else /** * @brief Creates a %vector with copies of an exemplar element. * @param n The number of elements to initially create. @@ -228,6 +262,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) const allocator_type& __a = allocator_type()) : _Base(__n, __a) { _M_fill_initialize(__n, __value); } +#endif /** * @brief %Vector copy constructor. @@ -538,6 +573,25 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) max_size() const { return _M_get_Tp_allocator().max_size(); } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Resizes the %vector to the specified number of elements. + * @param new_size Number of elements the %vector should contain. + * + * This function will %resize the %vector to the specified + * number of elements. If the number is smaller than the + * %vector's current size the %vector is truncated, otherwise + * default constructed elements are appended. + */ + void + resize(size_type __new_size) + { + if (__new_size > size()) + _M_default_append(__new_size - size()); + else if (__new_size < size()) + _M_erase_at_end(this->_M_impl._M_start + __new_size); + } + /** * @brief Resizes the %vector to the specified number of elements. * @param new_size Number of elements the %vector should contain. @@ -550,13 +604,34 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) * given data. */ void - resize(size_type __new_size, value_type __x = value_type()) + resize(size_type __new_size, const value_type& __x) { - if (__new_size < size()) + if (__new_size > size()) + insert(end(), __new_size - size(), __x); + else if (__new_size < size()) _M_erase_at_end(this->_M_impl._M_start + __new_size); - else + } +#else + /** + * @brief Resizes the %vector to the specified number of elements. + * @param new_size Number of elements the %vector should contain. + * @param x Data with which new elements should be populated. + * + * This function will %resize the %vector to the specified + * number of elements. If the number is smaller than the + * %vector's current size the %vector is truncated, otherwise + * the %vector is extended and new elements are populated with + * given data. + */ + void + resize(size_type __new_size, value_type __x = value_type()) + { + if (__new_size > size()) insert(end(), __new_size - size(), __x); + else if (__new_size < size()) + _M_erase_at_end(this->_M_impl._M_start + __new_size); } +#endif #ifdef __GXX_EXPERIMENTAL_CXX0X__ /** A non-binding request to reduce capacity() to size(). */ @@ -1049,6 +1124,16 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + // Called by the vector(n) constructor. + void + _M_default_initialize(size_type __n) + { + std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, + _M_get_Tp_allocator()); + this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; + } +#endif // Internal assign functions follow. The *_aux functions do the actual // assignment work for the range versions. @@ -1131,6 +1216,12 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + // Called by resize(n). + void + _M_default_append(size_type __n); +#endif + // Called by insert(p,x) #ifndef __GXX_EXPERIMENTAL_CXX0X__ void diff --git a/libstdc++-v3/include/bits/unique_ptr.h b/libstdc++-v3/include/bits/unique_ptr.h index 7b07ca477f4..ac62ff7f304 100644 --- a/libstdc++-v3/include/bits/unique_ptr.h +++ b/libstdc++-v3/include/bits/unique_ptr.h @@ -81,7 +81,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) class unique_ptr { typedef std::tuple<_Tp*, _Tp_Deleter> __tuple_type; - typedef _Tp* unique_ptr::* __unspecified_pointer_type; // use SFINAE to determine whether _Del::pointer exists class _Pointer @@ -126,6 +125,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { static_assert(!std::is_reference<deleter_type>::value, "rvalue deleter bound to reference"); } + unique_ptr(nullptr_t) + : _M_t(pointer(), deleter_type()) + { } + // Move constructors. unique_ptr(unique_ptr&& __u) : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { } @@ -157,7 +160,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } unique_ptr& - operator=(__unspecified_pointer_type) + operator=(nullptr_t) { reset(); return *this; @@ -230,11 +233,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // [unique.ptr.runtime] // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 740 - omit specialization for array objects with a compile time length - template<typename _Tp, typename _Tp_Deleter> + template<typename _Tp, typename _Tp_Deleter> class unique_ptr<_Tp[], _Tp_Deleter> { typedef std::tuple<_Tp*, _Tp_Deleter> __tuple_type; - typedef _Tp* unique_ptr::* __unspecified_pointer_type; public: typedef _Tp* pointer; @@ -264,6 +266,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { static_assert(!std::is_reference<deleter_type>::value, "rvalue deleter bound to reference"); } + /* TODO: use delegating constructor */ + unique_ptr(nullptr_t) + : _M_t(pointer(), deleter_type()) + { } + // Move constructors. unique_ptr(unique_ptr&& __u) : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { } @@ -295,7 +302,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } unique_ptr& - operator=(__unspecified_pointer_type) + operator=(nullptr_t) { reset(); return *this; @@ -338,7 +345,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { using std::swap; swap(std::get<0>(_M_t), __p); - if (__p != pointer()) + if (__p != nullptr) + get_deleter()(__p); + } + + void + reset(nullptr_t) + { + pointer __p = get(); + std::get<0>(_M_t) = pointer(); + if (__p != nullptr) get_deleter()(__p); } @@ -428,6 +444,19 @@ _GLIBCXX_BEGIN_NAMESPACE(std) const unique_ptr<_Up, _Up_Deleter>& __y) { return !(__x.get() < __y.get()); } + /// std::hash specialization for unique_ptr. + template<typename _Tp, typename _Tp_Deleter> + struct hash<unique_ptr<_Tp, _Tp_Deleter>> + : public std::unary_function<unique_ptr<_Tp, _Tp_Deleter>, size_t> + { + size_t + operator()(const unique_ptr<_Tp, _Tp_Deleter>& __u) const + { + typedef unique_ptr<_Tp, _Tp_Deleter> _UP; + return std::hash<typename _UP::pointer>()(__u.get()); + } + }; + // @} group pointer_abstractions _GLIBCXX_END_NAMESPACE diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 74998ff7725..80b970c8cf5 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -82,6 +82,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) { } + __unordered_map(const __unordered_map& __x) = default; + __unordered_map(__unordered_map&& __x) : _Base(std::forward<_Base>(__x)) { } }; @@ -137,6 +139,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) { } + __unordered_multimap(const __unordered_multimap& __x) = default; + __unordered_multimap(__unordered_multimap&& __x) : _Base(std::forward<_Base>(__x)) { } }; @@ -246,6 +250,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) : _Base(__f, __l, __n, __hf, __eql, __a) { } + unordered_map(const unordered_map& __x) = default; + unordered_map(unordered_map&& __x) : _Base(std::forward<_Base>(__x)) { } @@ -258,6 +264,9 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) { } unordered_map& + operator=(const unordered_map& __x) = default; + + unordered_map& operator=(unordered_map&& __x) { // NB: DR 1204. @@ -328,6 +337,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) : _Base(__f, __l, __n, __hf, __eql, __a) { } + unordered_multimap(const unordered_multimap& __x) = default; + unordered_multimap(unordered_multimap&& __x) : _Base(std::forward<_Base>(__x)) { } @@ -340,6 +351,9 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) { } unordered_multimap& + operator=(const unordered_multimap& __x) = default; + + unordered_multimap& operator=(unordered_multimap&& __x) { // NB: DR 1204. diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 50dee215e16..8682f2d7237 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -82,6 +82,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) std::_Identity<_Value>(), __a) { } + __unordered_set(const __unordered_set& __x) = default; + __unordered_set(__unordered_set&& __x) : _Base(std::forward<_Base>(__x)) { } }; @@ -135,6 +137,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) std::_Identity<_Value>(), __a) { } + __unordered_multiset(const __unordered_multiset& __x) = default; + __unordered_multiset(__unordered_multiset&& __x) : _Base(std::forward<_Base>(__x)) { } }; @@ -239,6 +243,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) : _Base(__f, __l, __n, __hf, __eql, __a) { } + unordered_set(const unordered_set& __x) = default; + unordered_set(unordered_set&& __x) : _Base(std::forward<_Base>(__x)) { } @@ -251,6 +257,9 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) { } unordered_set& + operator=(const unordered_set& __x) = default; + + unordered_set& operator=(unordered_set&& __x) { // NB: DR 1204. @@ -318,6 +327,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) : _Base(__f, __l, __n, __hf, __eql, __a) { } + unordered_multiset(const unordered_multiset& __x) = default; + unordered_multiset(unordered_multiset&& __x) : _Base(std::forward<_Base>(__x)) { } @@ -330,6 +341,9 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) { } unordered_multiset& + operator=(const unordered_multiset& __x) = default; + + unordered_multiset& operator=(unordered_multiset&& __x) { // NB: DR 1204. diff --git a/libstdc++-v3/include/bits/valarray_array.h b/libstdc++-v3/include/bits/valarray_array.h index a12b3347b9d..7aa61f14d81 100644 --- a/libstdc++-v3/include/bits/valarray_array.h +++ b/libstdc++-v3/include/bits/valarray_array.h @@ -1,7 +1,7 @@ // The template and inlines for the -*- C++ -*- internal _Array helper class. // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, -// 2006, 2007, 2008, 2009 +// 2006, 2007, 2008, 2009, 2010 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -127,7 +127,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) inline void __valarray_fill_construct(_Tp* __b, _Tp* __e, const _Tp __t) { - _Array_init_ctor<_Tp, __is_pod(_Tp)>::_S_do_it(__b, __e, __t); + _Array_init_ctor<_Tp, __is_trivial(_Tp)>::_S_do_it(__b, __e, __t); } // @@ -160,7 +160,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __valarray_copy_construct(const _Tp* __b, const _Tp* __e, _Tp* __restrict__ __o) { - _Array_copy_ctor<_Tp, __is_pod(_Tp)>::_S_do_it(__b, __e, __o); + _Array_copy_ctor<_Tp, __is_trivial(_Tp)>::_S_do_it(__b, __e, __o); } // copy-construct raw array [__o, *) from strided array __a[<__n : __s>] @@ -169,7 +169,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __valarray_copy_construct (const _Tp* __restrict__ __a, size_t __n, size_t __s, _Tp* __restrict__ __o) { - if (__is_pod(_Tp)) + if (__is_trivial(_Tp)) while (__n--) { *__o++ = *__a; @@ -190,7 +190,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) const size_t* __restrict__ __i, _Tp* __restrict__ __o, size_t __n) { - if (__is_pod(_Tp)) + if (__is_trivial(_Tp)) while (__n--) *__o++ = __a[*__i++]; else @@ -203,7 +203,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) inline void __valarray_destroy_elements(_Tp* __b, _Tp* __e) { - if (!__is_pod(_Tp)) + if (!__is_trivial(_Tp)) while (__b != __e) { __b->~_Tp(); @@ -267,7 +267,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __valarray_copy(const _Tp* __restrict__ __a, size_t __n, _Tp* __restrict__ __b) { - _Array_copier<_Tp, __is_pod(_Tp)>::_S_do_it(__a, __n, __b); + _Array_copier<_Tp, __is_trivial(_Tp)>::_S_do_it(__a, __n, __b); } // Copy strided array __a[<__n : __s>] in plain __b[<__n>] diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index e1097931048..846a0645d57 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -458,6 +458,59 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) } } +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<typename _Tp, typename _Alloc> + void + vector<_Tp, _Alloc>:: + _M_default_append(size_type __n) + { + if (__n != 0) + { + if (size_type(this->_M_impl._M_end_of_storage + - this->_M_impl._M_finish) >= __n) + { + std::__uninitialized_default_n_a(this->_M_impl._M_finish, + __n, _M_get_Tp_allocator()); + this->_M_impl._M_finish += __n; + } + else + { + const size_type __len = + _M_check_len(__n, "vector::_M_default_append"); + const size_type __old_size = this->size(); + pointer __new_start(this->_M_allocate(__len)); + pointer __new_finish(__new_start); + __try + { + __new_finish = + std::__uninitialized_move_a(this->_M_impl._M_start, + this->_M_impl._M_finish, + __new_start, + _M_get_Tp_allocator()); + std::__uninitialized_default_n_a(__new_finish, __n, + _M_get_Tp_allocator()); + __new_finish += __n; + } + __catch(...) + { + std::_Destroy(__new_start, __new_finish, + _M_get_Tp_allocator()); + _M_deallocate(__new_start, __len); + __throw_exception_again; + } + std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, + _M_get_Tp_allocator()); + _M_deallocate(this->_M_impl._M_start, + this->_M_impl._M_end_of_storage + - this->_M_impl._M_start); + this->_M_impl._M_start = __new_start; + this->_M_impl._M_finish = __new_finish; + this->_M_impl._M_end_of_storage = __new_start + __len; + } + } + } +#endif + template<typename _Tp, typename _Alloc> template<typename _InputIterator> void |