diff options
Diffstat (limited to 'libstdc++-v3/include')
32 files changed, 1520 insertions, 1111 deletions
diff --git a/libstdc++-v3/include/bits/allocator.h b/libstdc++-v3/include/bits/allocator.h index 28df242b1bc..c72859b6ed3 100644 --- a/libstdc++-v3/include/bits/allocator.h +++ b/libstdc++-v3/include/bits/allocator.h @@ -158,13 +158,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // To implement Option 3 of DR 431. template<typename _Alloc, bool = __is_empty(_Alloc)> struct __alloc_swap - { static void _S_do_it(_Alloc&, _Alloc&) { } }; + { static void _S_do_it(_Alloc&, _Alloc&) _GLIBCXX_NOEXCEPT { } }; template<typename _Alloc> struct __alloc_swap<_Alloc, false> { static void - _S_do_it(_Alloc& __one, _Alloc& __two) + _S_do_it(_Alloc& __one, _Alloc& __two) _GLIBCXX_NOEXCEPT { // Precondition: swappable allocators. if (__one != __two) @@ -194,13 +194,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = __or_<is_copy_constructible<typename _Tp::value_type>, is_nothrow_move_constructible<typename _Tp::value_type>>::value> struct __shrink_to_fit_aux - { static bool _S_do_it(_Tp&) { return false; } }; + { static bool _S_do_it(_Tp&) noexcept { return false; } }; template<typename _Tp> struct __shrink_to_fit_aux<_Tp, true> { static bool - _S_do_it(_Tp& __c) + _S_do_it(_Tp& __c) noexcept { __try { diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h index c8723ededd9..48904288867 100644 --- a/libstdc++-v3/include/bits/basic_string.h +++ b/libstdc++-v3/include/bits/basic_string.h @@ -178,7 +178,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static size_type _S_empty_rep_storage[]; static _Rep& - _S_empty_rep() + _S_empty_rep() _GLIBCXX_NOEXCEPT { // NB: Mild hack to avoid strict-aliasing warnings. Note that // _S_empty_rep_storage is never modified and the punning should @@ -188,23 +188,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } bool - _M_is_leaked() const + _M_is_leaked() const _GLIBCXX_NOEXCEPT { return this->_M_refcount < 0; } bool - _M_is_shared() const + _M_is_shared() const _GLIBCXX_NOEXCEPT { return this->_M_refcount > 0; } void - _M_set_leaked() + _M_set_leaked() _GLIBCXX_NOEXCEPT { this->_M_refcount = -1; } void - _M_set_sharable() + _M_set_sharable() _GLIBCXX_NOEXCEPT { this->_M_refcount = 0; } void - _M_set_length_and_sharable(size_type __n) + _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT { #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 if (__builtin_expect(this != &_S_empty_rep(), false)) @@ -234,7 +234,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _S_create(size_type, size_type, const _Alloc&); void - _M_dispose(const _Alloc& __a) + _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT { #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 if (__builtin_expect(this != &_S_empty_rep(), false)) @@ -271,7 +271,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Use empty-base optimization: http://www.cantrip.org/emptyopt.html struct _Alloc_hider : _Alloc { - _Alloc_hider(_CharT* __dat, const _Alloc& __a) + _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT : _Alloc(__a), _M_p(__dat) { } _CharT* _M_p; // The actual data. @@ -289,25 +289,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION mutable _Alloc_hider _M_dataplus; _CharT* - _M_data() const + _M_data() const _GLIBCXX_NOEXCEPT { return _M_dataplus._M_p; } _CharT* - _M_data(_CharT* __p) + _M_data(_CharT* __p) _GLIBCXX_NOEXCEPT { return (_M_dataplus._M_p = __p); } _Rep* - _M_rep() const + _M_rep() const _GLIBCXX_NOEXCEPT { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); } // For the internal use we have functions similar to `begin'/`end' // but they do not call _M_leak. iterator - _M_ibegin() const + _M_ibegin() const _GLIBCXX_NOEXCEPT { return iterator(_M_data()); } iterator - _M_iend() const + _M_iend() const _GLIBCXX_NOEXCEPT { return iterator(_M_data() + this->size()); } void @@ -334,7 +334,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // NB: _M_limit doesn't check for a bad __pos value. size_type - _M_limit(size_type __pos, size_type __off) const + _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT { const bool __testoff = __off < this->size() - __pos; return __testoff ? __off : this->size() - __pos; @@ -342,7 +342,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // True if _Rep and source do not overlap. bool - _M_disjunct(const _CharT* __s) const + _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT { return (less<const _CharT*>()(__s, _M_data()) || less<const _CharT*>()(_M_data() + this->size(), __s)); @@ -351,7 +351,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // When __n = 1 way faster than the general multichar // traits_type::copy/move/assign. static void - _M_copy(_CharT* __d, const _CharT* __s, size_type __n) + _M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT { if (__n == 1) traits_type::assign(*__d, *__s); @@ -360,7 +360,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } static void - _M_move(_CharT* __d, const _CharT* __s, size_type __n) + _M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT { if (__n == 1) traits_type::assign(*__d, *__s); @@ -369,7 +369,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } static void - _M_assign(_CharT* __d, size_type __n, _CharT __c) + _M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT { if (__n == 1) traits_type::assign(*__d, __c); @@ -382,29 +382,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<class _Iterator> static void _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2) + _GLIBCXX_NOEXCEPT { for (; __k1 != __k2; ++__k1, ++__p) traits_type::assign(*__p, *__k1); // These types are off. } static void - _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) + _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT { _S_copy_chars(__p, __k1.base(), __k2.base()); } static void _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2) + _GLIBCXX_NOEXCEPT { _S_copy_chars(__p, __k1.base(), __k2.base()); } static void - _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) + _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT { _M_copy(__p, __k1, __k2 - __k1); } static void _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2) + _GLIBCXX_NOEXCEPT { _M_copy(__p, __k1, __k2 - __k1); } static int - _S_compare(size_type __n1, size_type __n2) + _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT { const difference_type __d = difference_type(__n1 - __n2); @@ -423,7 +426,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_leak_hard(); static _Rep& - _S_empty_rep() + _S_empty_rep() _GLIBCXX_NOEXCEPT { return _Rep::_S_empty_rep(); } public: @@ -756,7 +759,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus >= 201103L /// A non-binding request to reduce capacity() to size(). void - shrink_to_fit() + shrink_to_fit() _GLIBCXX_NOEXCEPT { if (capacity() > size()) { @@ -799,6 +802,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * Erases the string, making it empty. */ + // PR 56166: this should not throw. void clear() _GLIBCXX_NOEXCEPT { _M_mutate(0, this->size(), 0); } @@ -823,7 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * see at().) */ const_reference - operator[] (size_type __pos) const + operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT { _GLIBCXX_DEBUG_ASSERT(__pos <= size()); return _M_data()[__pos]; @@ -903,7 +907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * element of the %string. */ const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return operator[](0); } /** @@ -919,7 +923,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * last element of the %string. */ const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { return operator[](this->size() - 1); } #endif @@ -1787,6 +1791,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * Exchanges the contents of this string with that of @a __s in constant * time. */ + // PR 58265, this should be noexcept. void swap(basic_string& __s); diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 4d8ce2351e8..718dcec1e09 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -63,7 +63,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> void _List_base<_Tp, _Alloc>:: - _M_clear() + _M_clear() _GLIBCXX_NOEXCEPT { typedef _List_node<_Tp> _Node; _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next); @@ -145,7 +145,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>:: #if __cplusplus >= 201103L - erase(const_iterator __position) + erase(const_iterator __position) noexcept #else erase(iterator __position) #endif diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h index 412465adfa2..9d1438aab23 100644 --- a/libstdc++-v3/include/bits/regex.h +++ b/libstdc++-v3/include/bits/regex.h @@ -1004,6 +1004,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const basic_regex<_Cp, _Rp>&, regex_constants::match_flag_type); + template<typename, typename, typename, typename> + friend class __detail::_Executor; + + template<typename, typename, typename, typename> + friend class __detail::_DFSExecutor; + + template<typename, typename, typename, typename> + friend class __detail::_BFSExecutor; + flag_type _M_flags; _Rx_traits _M_traits; _AutomatonPtr _M_automaton; @@ -1783,21 +1792,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ explicit match_results(const _Alloc& __a = _Alloc()) - : _Base_type(__a) + : _Base_type(__a), _M_in_iterator(false) { } /** * @brief Copy constructs a %match_results. */ match_results(const match_results& __rhs) - : _Base_type(__rhs) + : _Base_type(__rhs), _M_in_iterator(false) { } /** * @brief Move constructs a %match_results. */ match_results(match_results&& __rhs) noexcept - : _Base_type(std::move(__rhs)) + : _Base_type(std::move(__rhs)), _M_in_iterator(false) { } /** @@ -1905,8 +1914,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION difference_type position(size_type __sub = 0) const { - return __sub < size() ? std::distance(this->prefix().first, - (*this)[__sub].first) : -1; + // [28.12.1.4.5] + if (_M_in_iterator) + return __sub < size() ? std::distance(_M_begin, + (*this)[__sub].first) : -1; + else + return __sub < size() ? std::distance(this->prefix().first, + (*this)[__sub].first) : -1; } /** @@ -2106,19 +2120,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename, typename, typename, typename> friend class __detail::_BFSExecutor; - template<typename _Bp, typename _Ap, typename _Ch_type, typename _Rx_traits> + template<typename, typename, typename> + friend class regex_iterator; + + template<typename _Bp, typename _Ap, + typename _Ch_type, typename _Rx_traits> friend bool regex_match(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Ch_type, _Rx_traits>&, regex_constants::match_flag_type); - template<typename _Bp, typename _Ap, typename _Ch_type, typename _Rx_traits> + template<typename _Bp, typename _Ap, + typename _Ch_type, typename _Rx_traits> friend bool regex_search(_Bp, _Bp, match_results<_Bp, _Ap>&, const basic_regex<_Ch_type, _Rx_traits>&, regex_constants::match_flag_type); + + _Bi_iter _M_begin; + bool _M_in_iterator; }; typedef match_results<const char*> cmatch; @@ -2198,8 +2220,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @retval false Otherwise. * * @throws an exception of type regex_error. - * - * @todo Implement this function. */ template<typename _Bi_iter, typename _Alloc, typename _Ch_type, typename _Rx_traits> @@ -2213,8 +2233,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { if (__re._M_automaton == nullptr) return false; - __detail::__get_executor(__s, __e, __m, __re, __flags)->_M_match(); - if (__m.size() > 0 && __m[0].matched) + + auto __size = __re._M_automaton->_M_sub_count(); + __size += 2; + __m.resize(__size); + for (decltype(__size) __i = 0; __i < __size; ++__i) + __m.at(__i).matched = false; + + if (__detail::__get_executor(__s, __e, __m, __re, __flags)->_M_match()) { for (auto __it : __m) if (!__it.matched) @@ -2359,8 +2385,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * undefined. * * @throws an exception of type regex_error. - * - * @todo Implement this function. */ template<typename _Bi_iter, typename _Alloc, typename _Ch_type, typename _Rx_traits> @@ -2373,29 +2397,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { if (__re._M_automaton == nullptr) return false; - auto __cur = __first; - // Continue when __cur == __last - do + + auto __size = __re._M_automaton->_M_sub_count(); + __size += 2; + __m.resize(__size); + for (decltype(__size) __i = 0; __i < __size; ++__i) + __m.at(__i).matched = false; + + if (__detail::__get_executor(__first, __last, __m, __re, __flags) + ->_M_search()) { - __detail::__get_executor(__cur, __last, __m, __re, __flags) - ->_M_search_from_first(); - if (__m.size() > 0 && __m[0].matched) - { - for (auto __it : __m) - if (!__it.matched) - __it.first = __it.second = __last; - __m.at(__m.size()).first = __first; - __m.at(__m.size()).second = __m[0].first; - __m.at(__m.size()+1).first = __m[0].second; - __m.at(__m.size()+1).second = __last; - __m.at(__m.size()).matched = - (__m.prefix().first != __m.prefix().second); - __m.at(__m.size()+1).matched = - (__m.suffix().first != __m.suffix().second); - return true; - } + for (auto __it : __m) + if (!__it.matched) + __it.first = __it.second = __last; + __m.at(__m.size()).first = __first; + __m.at(__m.size()).second = __m[0].first; + __m.at(__m.size()+1).first = __m[0].second; + __m.at(__m.size()+1).second = __last; + __m.at(__m.size()).matched = + (__m.prefix().first != __m.prefix().second); + __m.at(__m.size()+1).matched = + (__m.suffix().first != __m.suffix().second); + return true; } - while (__cur++ != __last); return false; } @@ -2683,7 +2707,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION regex_iterator<_Bi_iter, _Ch_type, _Rx_traits>:: operator++() { - // FIXME: In all cases in which the call to regex_search returns true, + // In all cases in which the call to regex_search returns true, // match.prefix().first shall be equal to the previous value of // match[0].second, and for each index i in the half-open range // [0, match.size()) for which match[i].matched is true, @@ -2703,12 +2727,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (regex_search(__start, _M_end, _M_match, *_M_pregex, _M_flags | regex_constants::match_not_null | regex_constants::match_continuous)) - return *this; + { + _M_match._M_in_iterator = true; + _M_match._M_begin = _M_begin; + return *this; + } else ++__start; } _M_flags |= regex_constants::match_prev_avail; - if (!regex_search(__start, _M_end, _M_match, *_M_pregex, _M_flags)) + if (regex_search(__start, _M_end, _M_match, *_M_pregex, _M_flags)) + { + _M_match._M_in_iterator = true; + _M_match._M_begin = _M_begin; + } + else _M_match = value_type(); } return *this; diff --git a/libstdc++-v3/include/bits/regex_automaton.h b/libstdc++-v3/include/bits/regex_automaton.h index 2c872aa9482..94a14ce96aa 100644 --- a/libstdc++-v3/include/bits/regex_automaton.h +++ b/libstdc++-v3/include/bits/regex_automaton.h @@ -51,13 +51,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// that represents the regular expression. enum _Opcode { - _S_opcode_unknown = 0, - _S_opcode_alternative = 1, - _S_opcode_backref = 2, - _S_opcode_subexpr_begin = 4, - _S_opcode_subexpr_end = 5, - _S_opcode_match = 100, - _S_opcode_accept = 255 + _S_opcode_unknown, + _S_opcode_alternative, + _S_opcode_backref, + _S_opcode_line_begin_assertion, + _S_opcode_line_end_assertion, + _S_opcode_word_boundry, + _S_opcode_subexpr_lookahead, + _S_opcode_subexpr_begin, + _S_opcode_subexpr_end, + _S_opcode_dummy, + _S_opcode_match, + _S_opcode_accept, }; template<typename _CharT, typename _TraitsT> @@ -69,37 +74,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _OpcodeT _M_opcode; // type of outgoing transition _StateIdT _M_next; // outgoing transition - union // Since they are mutual exclusive. + union // Since they are mutually exclusive. { - _StateIdT _M_alt; // for _S_opcode_alternative unsigned int _M_subexpr; // for _S_opcode_subexpr_* unsigned int _M_backref_index; // for _S_opcode_backref + struct + { + // for _S_opcode_alternative. + _StateIdT _M_quant_index; + // for _S_opcode_alternative or _S_opcode_subexpr_lookahead + _StateIdT _M_alt; + // for _S_opcode_word_boundry or _S_opcode_subexpr_lookahead or + // quantifiers(ungreedy if set true) + bool _M_neg; + }; }; - _MatcherT _M_matches; // for _S_opcode_match + _MatcherT _M_matches; // for _S_opcode_match explicit _State(_OpcodeT __opcode) : _M_opcode(__opcode), _M_next(_S_invalid_state_id) { } - _State(const _MatcherT& __m) - : _M_opcode(_S_opcode_match), _M_next(_S_invalid_state_id), - _M_matches(__m) - { } - - _State(_OpcodeT __opcode, unsigned __index) - : _M_opcode(__opcode), _M_next(_S_invalid_state_id) - { - if (__opcode == _S_opcode_subexpr_begin - || __opcode == _S_opcode_subexpr_end) - _M_subexpr = __index; - else if (__opcode == _S_opcode_backref) - _M_backref_index = __index; - } - - _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; @@ -140,7 +135,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _NFA(_FlagT __f) : _M_flags(__f), _M_start_state(0), _M_subexpr_count(0), - _M_has_backref(false) + _M_has_backref(false), _M_quant_count(0) { } _FlagT @@ -162,23 +157,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _StateIdT _M_insert_accept() { - this->push_back(_StateT(_S_opcode_accept)); - _M_accepting_states.insert(this->size()-1); - return this->size()-1; + auto __ret = _M_insert_state(_StateT(_S_opcode_accept)); + _M_accepting_states.insert(__ret); + return __ret; } _StateIdT - _M_insert_alt(_StateIdT __next, _StateIdT __alt) + _M_insert_alt(_StateIdT __next, _StateIdT __alt, bool __neg) { - this->push_back(_StateT(__next, __alt)); - return this->size()-1; + _StateT __tmp(_S_opcode_alternative); + // It labels every quantifier to make greedy comparison easier in BFS + // approach. + __tmp._M_quant_index = _M_quant_count++; + __tmp._M_next = __next; + __tmp._M_alt = __alt; + __tmp._M_neg = __neg; + return _M_insert_state(__tmp); } _StateIdT _M_insert_matcher(_MatcherT __m) { - this->push_back(_StateT(__m)); - return this->size()-1; + _StateT __tmp(_S_opcode_match); + __tmp._M_matches = __m; + return _M_insert_state(__tmp); } _StateIdT @@ -186,21 +188,63 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { auto __id = _M_subexpr_count++; _M_paren_stack.push_back(__id); - this->push_back(_StateT(_S_opcode_subexpr_begin, __id)); - return this->size()-1; + _StateT __tmp(_S_opcode_subexpr_begin); + __tmp._M_subexpr = __id; + return _M_insert_state(__tmp); } _StateIdT _M_insert_subexpr_end() { - this->push_back(_StateT(_S_opcode_subexpr_end, _M_paren_stack.back())); + _StateT __tmp(_S_opcode_subexpr_end); + __tmp._M_subexpr = _M_paren_stack.back(); _M_paren_stack.pop_back(); - return this->size()-1; + return _M_insert_state(__tmp); } _StateIdT _M_insert_backref(unsigned int __index); + _StateIdT + _M_insert_line_begin() + { return _M_insert_state(_StateT(_S_opcode_line_begin_assertion)); } + + _StateIdT + _M_insert_line_end() + { return _M_insert_state(_StateT(_S_opcode_line_end_assertion)); } + + _StateIdT + _M_insert_word_bound(bool __neg) + { + _StateT __tmp(_S_opcode_word_boundry); + __tmp._M_neg = __neg; + return _M_insert_state(__tmp); + } + + _StateIdT + _M_insert_lookahead(_StateIdT __alt, bool __neg) + { + _StateT __tmp(_S_opcode_subexpr_lookahead); + __tmp._M_alt = __alt; + __tmp._M_neg = __neg; + return _M_insert_state(__tmp); + } + + _StateIdT + _M_insert_dummy() + { return _M_insert_state(_StateT(_S_opcode_dummy)); } + + _StateIdT + _M_insert_state(_StateT __s) + { + this->push_back(__s); + return this->size()-1; + } + + // Eliminate dummy node in this NFA to make it compact. + void + _M_eliminate_dummy(); + #ifdef _GLIBCXX_DEBUG std::ostream& _M_dot(std::ostream& __ostr) const; @@ -211,6 +255,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _FlagT _M_flags; _StateIdT _M_start_state; _SizeT _M_subexpr_count; + _SizeT _M_quant_count; bool _M_has_backref; }; @@ -222,58 +267,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { public: typedef _NFA<_CharT, _TraitsT> _RegexT; - public: - // Constructs a single-node sequence - _StateSeq(_RegexT& __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) + public: + _StateSeq(_RegexT& __nfa, _StateIdT __s) + : _StateSeq(__nfa, __s, __s) { } - // 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(_RegexT& __nfa, _StateIdT __s, _StateIdT __end) + : _M_nfa(__nfa), _M_start(__s), _M_end(__end) { } - _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. + // Append a state on *this and change *this to the new sequence. void - _M_append(_StateIdT __id); + _M_append(_StateIdT __id) + { + _M_nfa[_M_end]._M_next = __id; + _M_end = __id; + } + // Append a sequence on *this and change *this to the new sequence. void - _M_append(_StateSeq& __rhs); + _M_append(const _StateSeq& __s) + { + _M_nfa[_M_end]._M_next = __s._M_start; + _M_end = __s._M_end; + } // Clones an entire sequence. - _StateIdT + _StateSeq _M_clone(); - private: + public: _RegexT& _M_nfa; _StateIdT _M_start; - _StateIdT _M_end1; - _StateIdT _M_end2; + _StateIdT _M_end; }; //@} regex-detail diff --git a/libstdc++-v3/include/bits/regex_automaton.tcc b/libstdc++-v3/include/bits/regex_automaton.tcc index 2c25d97549c..13af984c273 100644 --- a/libstdc++-v3/include/bits/regex_automaton.tcc +++ b/libstdc++-v3/include/bits/regex_automaton.tcc @@ -80,6 +80,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION << __id << " -> " << _M_alt << " [label=\"epsilon\", tailport=\"n\"];\n"; break; + case _S_opcode_backref: + __ostr << __id << " [label=\"" << __id << "\\nBACKREF " + << _M_subexpr << "\"];\n" + << __id << " -> " << _M_next << " [label=\"<match>\"];\n"; + break; + case _S_opcode_line_begin_assertion: + __ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n" + << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; + break; + case _S_opcode_line_end_assertion: + __ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n" + << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; + break; + case _S_opcode_word_boundry: + __ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY " + << _M_neg << "\"];\n" + << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; + break; + case _S_opcode_subexpr_lookahead: + __ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n" + << __id << " -> " << _M_next + << " [label=\"epsilon\", tailport=\"s\"];\n" + << __id << " -> " << _M_alt + << " [label=\"<assert>\", tailport=\"n\"];\n"; + break; case _S_opcode_subexpr_begin: __ostr << __id << " [label=\"" << __id << "\\nSBEGIN " << _M_subexpr << "\"];\n" @@ -90,10 +115,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION << _M_subexpr << "\"];\n" << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; break; - case _S_opcode_backref: - __ostr << __id << " [label=\"" << __id << "\\nBACKREF " - << _M_subexpr << "\"];\n" - << __id << " -> " << _M_next << " [label=\"<match>\"];\n"; + case _S_opcode_dummy: break; case _S_opcode_match: __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n" @@ -103,8 +125,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ; break; default: - __ostr << __id << " [label=\"" << __id << "\\nUNK\"];\n" - << __id << " -> " << _M_next << " [label=\"?\"];\n"; + _GLIBCXX_DEBUG_ASSERT(false); break; } return __ostr; @@ -140,71 +161,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__index == __it) __throw_regex_error(regex_constants::error_backref); _M_has_backref = true; - this->push_back(_StateT(_S_opcode_backref, __index)); - return this->size()-1; - } - - template<typename _CharT, typename _TraitsT> - _StateSeq<_CharT, _TraitsT>& _StateSeq<_CharT, _TraitsT>:: - operator=(const _StateSeq& __rhs) - { - _M_start = __rhs._M_start; - _M_end1 = __rhs._M_end1; - _M_end2 = __rhs._M_end2; - return *this; + _StateT __tmp(_S_opcode_backref); + __tmp._M_backref_index = __index; + return _M_insert_state(__tmp); } template<typename _CharT, typename _TraitsT> - void _StateSeq<_CharT, _TraitsT>:: - _M_push_back(_StateIdT __id) + void _NFA<_CharT, _TraitsT>:: + _M_eliminate_dummy() { - if (_M_end1 != _S_invalid_state_id) - _M_nfa[_M_end1]._M_next = __id; - _M_end1 = __id; + for (auto& __it : *this) + { + while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode + == _S_opcode_dummy) + __it._M_next = (*this)[__it._M_next]._M_next; + if (__it._M_opcode == _S_opcode_alternative) + while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode + == _S_opcode_dummy) + __it._M_alt = (*this)[__it._M_alt]._M_next; + } } + // Just apply DFS on the sequence and re-link their links. template<typename _CharT, typename _TraitsT> - void _StateSeq<_CharT, _TraitsT>:: - _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; - } - - template<typename _CharT, typename _TraitsT> - void _StateSeq<_CharT, _TraitsT>:: - _M_append(_StateSeq& __rhs) + _StateSeq<_CharT, _TraitsT> _StateSeq<_CharT, _TraitsT>:: + _M_clone() { - 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; + std::map<_StateIdT, _StateIdT> __m; + std::stack<_StateIdT> __stack; + __stack.push(_M_start); + while (!__stack.empty()) + { + auto __u = __stack.top(); + __stack.pop(); + auto __dup = _M_nfa[__u]; + auto __id = _M_nfa._M_insert_state(__dup); + __m[__u] = __id; + if (__u == _M_end) + continue; + if (__m.count(__dup._M_next) == 0) + __stack.push(__dup._M_next); + if (__dup._M_opcode == _S_opcode_alternative) + if (__m.count(__dup._M_alt) == 0) + __stack.push(__dup._M_alt); + } + for (auto __it : __m) + { + auto& __ref = _M_nfa[__it.second]; + if (__ref._M_next != -1) + { + _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_next)); + __ref._M_next = __m[__ref._M_next]; + } + if (__ref._M_opcode == _S_opcode_alternative) + if (__ref._M_alt != -1) + { + _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_alt)); + __ref._M_alt = __m[__ref._M_alt]; + } + } + return _StateSeq(_M_nfa, __m[_M_start], __m[_M_end]); } - // @todo implement this function. - template<typename _CharT, typename _TraitsT> - _StateIdT _StateSeq<_CharT, _TraitsT>:: - _M_clone() - { return 0; } - _GLIBCXX_END_NAMESPACE_VERSION } // namespace __detail } // namespace diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h index 55ecdb92d41..3b85d3a46c3 100644 --- a/libstdc++-v3/include/bits/regex_compiler.h +++ b/libstdc++-v3/include/bits/regex_compiler.h @@ -56,7 +56,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::shared_ptr<_RegexT> _M_get_nfa() const - { return std::shared_ptr<_RegexT>(new _RegexT(_M_state_store)); } + { return make_shared<_RegexT>(_M_nfa); } private: typedef _Scanner<_FwdIter> _ScannerT; @@ -64,6 +64,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef _StateSeq<_CharT, _TraitsT> _StateSeqT; typedef std::stack<_StateSeqT, std::vector<_StateSeqT>> _StackT; typedef _BracketMatcher<_CharT, _TraitsT> _BMatcherT; + typedef std::ctype<_CharT> _CtypeT; // accepts a specific token or returns false. bool @@ -91,21 +92,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bracket_expression(); void - _M_bracket_list(_BMatcherT& __matcher); - - bool - _M_follow_list(_BMatcherT& __matcher); - - void _M_expression_term(_BMatcherT& __matcher); bool _M_range_expression(_BMatcherT& __matcher); bool - _M_start_range(_BMatcherT& __matcher); - - bool _M_collating_symbol(_BMatcherT& __matcher); bool @@ -120,12 +112,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION bool _M_try_char(); - _CharT - _M_get_char(); + _StateSeqT + _M_pop() + { + auto ret = _M_stack.top(); + _M_stack.pop(); + return ret; + } const _TraitsT& _M_traits; + const _CtypeT& _M_ctype; _ScannerT _M_scanner; - _RegexT _M_state_store; + _RegexT _M_nfa; _StringT _M_value; _StackT _M_stack; _FlagT _M_flags; diff --git a/libstdc++-v3/include/bits/regex_compiler.tcc b/libstdc++-v3/include/bits/regex_compiler.tcc index e41b251c257..7f9a19af2d9 100644 --- a/libstdc++-v3/include/bits/regex_compiler.tcc +++ b/libstdc++-v3/include/bits/regex_compiler.tcc @@ -28,6 +28,31 @@ * Do not attempt to use it directly. @headername{regex} */ +// FIXME make comments doxygen format. + +// This compiler refers to "Regular Expression Matching Can Be Simple And Fast" +// (http://swtch.com/~rsc/regexp/regexp1.html"), +// but doesn't strictly follow it. +// +// When compiling, states are *chained* instead of tree- or graph-constructed. +// It's more like structured programs: there's if statement and loop statement. +// +// For alternative structure(say "a|b"), aka "if statement", two branchs should +// be constructed. However, these two shall merge to an "end_tag" at the end of +// this operator: +// +// branch1 +// / \ +// => begin_tag end_tag => +// \ / +// branch2 +// +// This is the difference between this implementation and that in Russ's +// article. +// +// That's why we introduced dummy node here ------ "end_tag" is a dummy node. +// All dummy node will be eliminated at the end of compiling process. + namespace std _GLIBCXX_VISIBILITY(default) { namespace __detail @@ -39,32 +64,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Compiler(_FwdIter __b, _FwdIter __e, const _TraitsT& __traits, _FlagT __flags) : _M_traits(__traits), _M_scanner(__b, __e, __flags, _M_traits.getloc()), - _M_state_store(__flags), _M_flags(__flags) + _M_ctype(std::use_facet<std::ctype<_CharT>>(_M_traits.getloc())), + _M_nfa(__flags), _M_flags(__flags) { - _StateSeqT __r(_M_state_store, - _M_state_store._M_insert_subexpr_begin()); - _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()); - __r._M_append(_M_state_store._M_insert_accept()); - } - - template<typename _FwdIter, typename _CharT, typename _TraitsT> - bool - _Compiler<_FwdIter, _CharT, _TraitsT>:: - _M_match_token(_TokenT token) - { - if (token == _M_scanner._M_get_token()) - { - _M_value = _M_scanner._M_get_value(); - _M_scanner._M_advance(); - return true; - } - return false; + _StateSeqT __r(_M_nfa, _M_nfa._M_start()); + __r._M_append(_M_nfa._M_insert_subexpr_begin()); + this->_M_disjunction(); + if (!_M_match_token(_ScannerT::_S_token_eof)) + __throw_regex_error(regex_constants::error_paren); + __r._M_append(_M_pop()); + _GLIBCXX_DEBUG_ASSERT(_M_stack.empty()); + __r._M_append(_M_nfa._M_insert_subexpr_end()); + __r._M_append(_M_nfa._M_insert_accept()); + _M_nfa._M_eliminate_dummy(); } template<typename _FwdIter, typename _CharT, typename _TraitsT> @@ -73,12 +85,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_disjunction() { this->_M_alternative(); - if (_M_match_token(_ScannerT::_S_token_or)) + // TODO empty alternative like, um, "(|asdf)" + while (_M_match_token(_ScannerT::_S_token_or)) { - _StateSeqT __alt1 = _M_stack.top(); _M_stack.pop(); - this->_M_disjunction(); - _StateSeqT __alt2 = _M_stack.top(); _M_stack.pop(); - _M_stack.push(_StateSeqT(__alt1, __alt2)); + _StateSeqT __alt1 = _M_pop(); + this->_M_alternative(); + _StateSeqT __alt2 = _M_pop(); + auto __end = _M_nfa._M_insert_dummy(); + __alt1._M_append(__end); + __alt2._M_append(__end); + _M_stack.push(_StateSeqT(_M_nfa, + _M_nfa._M_insert_alt(__alt1._M_start, + __alt2._M_start, false), + __end)); } } @@ -89,15 +108,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { if (this->_M_term()) { - _StateSeqT __re = _M_stack.top(); _M_stack.pop(); + _StateSeqT __re = _M_pop(); this->_M_alternative(); - if (!_M_stack.empty()) - { - __re._M_append(_M_stack.top()); - _M_stack.pop(); - } + __re._M_append(_M_pop()); _M_stack.push(__re); } + else + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_dummy())); } template<typename _FwdIter, typename _CharT, typename _TraitsT> @@ -115,13 +132,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return false; } - // TODO Implement it. template<typename _FwdIter, typename _CharT, typename _TraitsT> bool _Compiler<_FwdIter, _CharT, _TraitsT>:: _M_assertion() { - return false; + if (_M_match_token(_ScannerT::_S_token_line_begin)) + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. + _M_insert_line_begin())); + else if (_M_match_token(_ScannerT::_S_token_line_end)) + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. + _M_insert_line_end())); + else if (_M_match_token(_ScannerT::_S_token_word_bound)) + // _M_value[0] == 'n' means it's negtive, say "not word boundary". + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. + _M_insert_word_bound(_M_value[0] == 'n'))); + else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin)) + { + auto __neg = _M_value[0] == 'n'; + this->_M_disjunction(); + if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) + __throw_regex_error(regex_constants::error_paren); + auto __tmp = _M_pop(); + __tmp._M_append(_M_nfa._M_insert_accept()); + _M_stack.push( + _StateSeqT( + _M_nfa, + _M_nfa._M_insert_lookahead(__tmp._M_start, __neg))); + } + else + return false; + return true; } template<typename _FwdIter, typename _CharT, typename _TraitsT> @@ -129,71 +170,91 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Compiler<_FwdIter, _CharT, _TraitsT>:: _M_quantifier() { - if (_M_match_token(_ScannerT::_S_token_closure0)) + bool __neg = regex_constants::ECMAScript; + auto __init = [this, &__neg]() { if (_M_stack.empty()) __throw_regex_error(regex_constants::error_badrepeat); - _StateSeqT __r(_M_stack.top(), -1); - __r._M_append(__r._M_front()); - _M_stack.pop(); + __neg = __neg && _M_match_token(_ScannerT::_S_token_opt); + }; + if (_M_match_token(_ScannerT::_S_token_closure0)) + { + __init(); + auto __e = _M_pop(); + _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id, + __e._M_start, __neg)); + __e._M_append(__r); _M_stack.push(__r); - return; } - if (_M_match_token(_ScannerT::_S_token_closure1)) + else if (_M_match_token(_ScannerT::_S_token_closure1)) { - if (_M_stack.empty()) - __throw_regex_error(regex_constants::error_badrepeat); - _StateSeqT __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; + __init(); + auto __e = _M_pop(); + __e._M_append(_M_nfa._M_insert_alt(_S_invalid_state_id, __e._M_start, + __neg)); + _M_stack.push(__e); } - if (_M_match_token(_ScannerT::_S_token_opt)) + else if (_M_match_token(_ScannerT::_S_token_opt)) { - if (_M_stack.empty()) - __throw_regex_error(regex_constants::error_badrepeat); - _StateSeqT __r(_M_stack.top(), -1); - _M_stack.pop(); + __init(); + auto __e = _M_pop(); + auto __end = _M_nfa._M_insert_dummy(); + _StateSeqT __r(_M_nfa, _M_nfa._M_insert_alt(_S_invalid_state_id, + __e._M_start, __neg)); + __e._M_append(__end); + __r._M_append(__end); _M_stack.push(__r); - return; } - if (_M_match_token(_ScannerT::_S_token_interval_begin)) + else if (_M_match_token(_ScannerT::_S_token_interval_begin)) { - if (_M_stack.empty()) - __throw_regex_error(regex_constants::error_badrepeat); + __init(); if (!_M_match_token(_ScannerT::_S_token_dup_count)) __throw_regex_error(regex_constants::error_badbrace); - _StateSeqT __r(_M_stack.top()); + _StateSeqT __r(_M_pop()); + _StateSeqT __e(_M_nfa, _M_nfa._M_insert_dummy()); int __min_rep = _M_cur_int_value(10); - for (int __i = 1; __i < __min_rep; ++__i) - _M_stack.top()._M_append(__r._M_clone()); + // {3 + for (int __i = 0; __i < __min_rep; ++__i) + __e._M_append(__r._M_clone()); if (_M_match_token(_ScannerT::_S_token_comma)) - if (_M_match_token(_ScannerT::_S_token_dup_count)) + if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7} { int __n = _M_cur_int_value(10) - __min_rep; if (__n < 0) __throw_regex_error(regex_constants::error_badbrace); + auto __end = _M_nfa._M_insert_dummy(); + // _M_alt is the "match more" branch, and _M_next is the + // "match less" one. Switch _M_alt and _M_next of all created + // nodes. This is a hacking but IMO works well. + std::stack<_StateIdT> __stack; for (int __i = 0; __i < __n; ++__i) { - _StateSeqT __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); + auto __tmp = __r._M_clone(); + auto __alt = _M_nfa._M_insert_alt(__tmp._M_start, + __end, __neg); + __stack.push(__alt); + __e._M_append(_StateSeqT(_M_nfa, __alt, __tmp._M_end)); + } + __e._M_append(__end); + while (!__stack.empty()) + { + auto& __tmp = _M_nfa[__stack.top()]; + __stack.pop(); + swap(__tmp._M_next, __tmp._M_alt); } } - else + else // {3,} { - _StateSeqT __r(_M_stack.top(), -1); - __r._M_push_back(__r._M_front()); - _M_stack.pop(); - _M_stack.push(__r); + auto __tmp = __r._M_clone(); + _StateSeqT __s(_M_nfa, + _M_nfa._M_insert_alt(_S_invalid_state_id, + __tmp._M_start, __neg)); + __tmp._M_append(__s); + __e._M_append(__s); } if (!_M_match_token(_ScannerT::_S_token_interval_end)) __throw_regex_error(regex_constants::error_brace); - return; + _M_stack.push(__e); } } @@ -203,46 +264,50 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_atom() { if (_M_match_token(_ScannerT::_S_token_anychar)) + _M_stack.push(_StateSeqT(_M_nfa, + _M_nfa._M_insert_matcher + (_AnyMatcher<_CharT, _TraitsT>(_M_traits)))); + else if (_M_try_char()) + _M_stack.push(_StateSeqT(_M_nfa, + _M_nfa._M_insert_matcher + (_CharMatcher<_CharT, _TraitsT>(_M_value[0], + _M_traits, + _M_flags)))); + else if (_M_match_token(_ScannerT::_S_token_backref)) + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa. + _M_insert_backref(_M_cur_int_value(10)))); + else if (_M_match_token(_ScannerT::_S_token_quoted_class)) { - _M_stack.push(_StateSeqT(_M_state_store, - _M_state_store._M_insert_matcher - (_AnyMatcher<_CharT, _TraitsT>(_M_traits)))); - return true; - } - if (_M_try_char()) - { - _M_stack.push(_StateSeqT(_M_state_store, - _M_state_store._M_insert_matcher - (_CharMatcher<_CharT, _TraitsT>(_M_value[0], - _M_traits, - _M_flags)))); - return true; + _GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1); + _BMatcherT __matcher(_M_ctype.is(_CtypeT::upper, _M_value[0]), + _M_traits, _M_flags); + __matcher._M_add_character_class(_M_value); + _M_stack.push(_StateSeqT(_M_nfa, + _M_nfa._M_insert_matcher(__matcher))); } - if (_M_match_token(_ScannerT::_S_token_backref)) + else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin)) { - _M_stack.push(_StateSeqT(_M_state_store, _M_state_store. - _M_insert_backref(_M_cur_int_value(10)))); - return true; + _StateSeqT __r(_M_nfa, _M_nfa._M_insert_dummy()); + this->_M_disjunction(); + if (!_M_match_token(_ScannerT::_S_token_subexpr_end)) + __throw_regex_error(regex_constants::error_paren); + __r._M_append(_M_pop()); + _M_stack.push(__r); } - if (_M_match_token(_ScannerT::_S_token_subexpr_begin)) + else if (_M_match_token(_ScannerT::_S_token_subexpr_begin)) { - int __mark = _M_state_store._M_sub_count(); - _StateSeqT __r(_M_state_store, - _M_state_store. - _M_insert_subexpr_begin()); + int __mark = _M_nfa._M_sub_count(); + _StateSeqT __r(_M_nfa, _M_nfa._M_insert_subexpr_begin()); 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()); + __r._M_append(_M_pop()); + __r._M_append(_M_nfa._M_insert_subexpr_end()); _M_stack.push(__r); - return true; } - return _M_bracket_expression(); + else if (!_M_bracket_expression()) + return false; + return true; } template<typename _FwdIter, typename _CharT, typename _TraitsT> @@ -255,51 +320,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin))) return false; _BMatcherT __matcher(__neg, _M_traits, _M_flags); - _M_bracket_list(__matcher); - _M_stack.push(_StateSeqT(_M_state_store, - _M_state_store._M_insert_matcher(__matcher))); + while (!_M_match_token(_ScannerT::_S_token_bracket_end)) + _M_expression_term(__matcher); + _M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_matcher(__matcher))); return true; } template<typename _FwdIter, typename _CharT, typename _TraitsT> void _Compiler<_FwdIter, _CharT, _TraitsT>:: - _M_bracket_list(_BMatcherT& __matcher) - { - if (_M_match_token(_ScannerT::_S_token_bracket_end)) - return; - _M_expression_term(__matcher); - _M_bracket_list(__matcher); - return; - } - - template<typename _FwdIter, typename _CharT, typename _TraitsT> - void - _Compiler<_FwdIter, _CharT, _TraitsT>:: _M_expression_term(_BMatcherT& __matcher) { if (_M_match_token(_ScannerT::_S_token_collsymbol)) - { - __matcher._M_add_collating_element(_M_value); - return; - } - if (_M_match_token(_ScannerT::_S_token_equiv_class_name)) - { - __matcher._M_add_equivalence_class(_M_value); - return; - } - if (_M_match_token(_ScannerT::_S_token_char_class_name)) - { - __matcher._M_add_character_class(_M_value); - return; - } - if (_M_try_char()) // [a + __matcher._M_add_collating_element(_M_value); + else if (_M_match_token(_ScannerT::_S_token_equiv_class_name)) + __matcher._M_add_equivalence_class(_M_value); + else if (_M_match_token(_ScannerT::_S_token_char_class_name)) + __matcher._M_add_character_class(_M_value); + else if (_M_try_char()) // [a { auto __ch = _M_value[0]; if (_M_try_char()) { - if (_M_value[0] == std::use_facet<std::ctype<_CharT>> - (_M_traits.getloc()).widen('-')) // [a- + if (_M_value[0] == '-') // [a- { if (_M_try_char()) // [a-z] { @@ -315,9 +358,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __matcher._M_add_char(_M_value[0]); } __matcher._M_add_char(__ch); - return; } - __throw_regex_error(regex_constants::error_brack); + else + __throw_regex_error(regex_constants::error_brack); } template<typename _FwdIter, typename _CharT, typename _TraitsT> @@ -342,6 +385,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _FwdIter, typename _CharT, typename _TraitsT> + bool + _Compiler<_FwdIter, _CharT, _TraitsT>:: + _M_match_token(_TokenT token) + { + if (token == _M_scanner._M_get_token()) + { + _M_value = _M_scanner._M_get_value(); + _M_scanner._M_advance(); + return true; + } + return false; + } + + template<typename _FwdIter, typename _CharT, typename _TraitsT> int _Compiler<_FwdIter, _CharT, _TraitsT>:: _M_cur_int_value(int __radix) diff --git a/libstdc++-v3/include/bits/regex_constants.h b/libstdc++-v3/include/bits/regex_constants.h index 23174becdf9..94c25e531b3 100644 --- a/libstdc++-v3/include/bits/regex_constants.h +++ b/libstdc++-v3/include/bits/regex_constants.h @@ -52,19 +52,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ //@{ 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 - }; + { + _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. @@ -78,87 +78,87 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * %set. */ enum syntax_option_type : unsigned int - { - /** - * Specifies that the matching of regular expressions against a character - * sequence shall be performed without regard to case. - */ - 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. - */ - 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. - */ - optimize = 1 << _S_optimize, - - /** - * Specifies that character ranges of the form [a-b] should be locale - * sensitive. - */ - 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. - */ - 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]. - */ - 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. - */ - 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, \\&apos,, &apos,, - * and \\ddd (where ddd is one, two, or three octal digits). - */ - 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. - */ - 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. - */ - egrep = 1 << _S_egrep, - }; + { + /** + * Specifies that the matching of regular expressions against a character + * sequence shall be performed without regard to case. + */ + 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. + */ + 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. + */ + optimize = 1 << _S_optimize, + + /** + * Specifies that character ranges of the form [a-b] should be locale + * sensitive. + */ + 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. + */ + 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]. + */ + 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. + */ + 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, \\&apos,, &apos,, + * and \\ddd (where ddd is one, two, or three octal digits). + */ + 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. + */ + 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. + */ + egrep = 1 << _S_egrep, + }; constexpr inline syntax_option_type operator&(syntax_option_type __a, syntax_option_type __b) @@ -211,20 +211,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION //@{ 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 - }; + { + _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. @@ -233,110 +233,148 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * 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. - */ - constexpr 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). - */ - constexpr 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). - */ - constexpr match_flag_type match_not_eol = 1 << _S_not_eol; - - /** - * The expression \\b is not matched against the sub-sequence - * [first,first). - */ - constexpr match_flag_type match_not_bow = 1 << _S_not_bow; - - /** - * The expression \\b should not be matched against the sub-sequence - * [last,last). - */ - constexpr match_flag_type match_not_eow = 1 << _S_not_eow; - - /** - * If more than one match is possible then any match is an acceptable - * result. - */ - constexpr match_flag_type match_any = 1 << _S_any; - - /** - * The expression does not match an empty sequence. - */ - constexpr match_flag_type match_not_null = 1 << _S_not_null; + enum match_flag_type : unsigned int + { + /** + * The default matching rules. + */ + 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). + */ + 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). + */ + match_not_eol = 1 << _S_not_eol, + + /** + * The expression \\b is not matched against the sub-sequence + * [first,first). + */ + match_not_bow = 1 << _S_not_bow, + + /** + * The expression \\b should not be matched against the sub-sequence + * [last,last). + */ + match_not_eow = 1 << _S_not_eow, + + /** + * If more than one match is possible then any match is an acceptable + * result. + */ + match_any = 1 << _S_any, + + /** + * The expression does not match an empty sequence. + */ + match_not_null = 1 << _S_not_null, + + /** + * The expression only matches a sub-sequence that begins at first . + */ + 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 28.11 and iterators 28.12. + */ + 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. + */ + 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]. + */ + 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. + */ + 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. + */ + format_first_only = 1 << _S_first_only, + }; + + constexpr inline match_flag_type + operator&(match_flag_type __a, match_flag_type __b) + { + return (match_flag_type)(static_cast<unsigned int>(__a) + & static_cast<unsigned int>(__b)); + } - /** - * The expression only matches a sub-sequence that begins at first . - */ - constexpr match_flag_type match_continuous = 1 << _S_continuous; + constexpr inline match_flag_type + operator|(match_flag_type __a, match_flag_type __b) + { + return (match_flag_type)(static_cast<unsigned int>(__a) + | static_cast<unsigned int>(__b)); + } - /** - * --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 28.11 and iterators 28.12. - */ - constexpr match_flag_type match_prev_avail = 1 << _S_prev_avail; + constexpr inline match_flag_type + operator^(match_flag_type __a, match_flag_type __b) + { + return (match_flag_type)(static_cast<unsigned int>(__a) + ^ static_cast<unsigned int>(__b)); + } - /** - * 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. - */ - constexpr match_flag_type format_default = 0; + constexpr inline match_flag_type + operator~(match_flag_type __a) + { return (match_flag_type)(~static_cast<unsigned int>(__a)); } - /** - * 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]. - */ - constexpr match_flag_type format_sed = 1 << _S_sed; + inline match_flag_type& + operator&=(match_flag_type& __a, match_flag_type __b) + { return __a = __a & __b; } - /** - * 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. - */ - constexpr match_flag_type format_no_copy = 1 << _S_no_copy; + inline match_flag_type& + operator|=(match_flag_type& __a, match_flag_type __b) + { return __a = __a | __b; } - /** - * When specified during a search and replace operation, only the first - * occurrence of the regular expression shall be replaced. - */ - constexpr match_flag_type format_first_only = 1 << _S_first_only; + inline match_flag_type& + operator^=(match_flag_type& __a, match_flag_type __b) + { return __a = __a ^ __b; } //@} diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h index 6d66d881584..b8e9266f910 100644 --- a/libstdc++-v3/include/bits/regex_executor.h +++ b/libstdc++-v3/include/bits/regex_executor.h @@ -28,7 +28,11 @@ * Do not attempt to use it directly. @headername{regex} */ -// TODO: convert comments to doxygen format. +// FIXME convert comments to doxygen format. + +// TODO Put _DFSExecutor and _BFSExecutor into one class. They are becoming +// much more similar. Also, make grouping seperated. The +// regex_constants::nosubs enables much more simpler execution. namespace std _GLIBCXX_VISIBILITY(default) { @@ -57,42 +61,107 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION class _Executor { public: + typedef basic_regex<_CharT, _TraitsT> _RegexT; typedef match_results<_BiIter, _Alloc> _ResultsT; typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec; typedef regex_constants::match_flag_type _FlagT; + typedef typename _TraitsT::char_class_type _ClassT; - virtual - ~_Executor() + public: + _Executor(_BiIter __begin, + _BiIter __end, + _ResultsT& __results, + const _RegexT& __re, + _FlagT __flags) + : _M_begin(__begin), + _M_end(__end), + _M_results(__results), + _M_re(__re), + _M_flags(__flags) { } // Set matched when string exactly match the pattern. - virtual void - _M_match() = 0; + bool + _M_match() + { + _M_match_mode = true; + _M_init(_M_begin); + return _M_main(); + } // Set matched when some prefix of the string matches the pattern. - virtual void - _M_search_from_first() = 0; - - protected: - typedef typename _NFA<_CharT, _TraitsT>::_SizeT _SizeT; - _Executor(_BiIter __begin, - _BiIter __end, - _ResultsT& __results, - _FlagT __flags, - _SizeT __size) - : _M_current(__begin), _M_end(__end), _M_results(__results), - _M_flags(__flags) + bool + _M_search_from_first() { - __size += 2; - _M_results.resize(__size); - for (auto __i = 0; __i < __size; __i++) - _M_results[__i].matched = false; + _M_match_mode = false; + _M_init(_M_begin); + return _M_main(); } - _BiIter _M_current; - _BiIter _M_end; - _ResultsVec& _M_results; - _FlagT _M_flags; + bool + _M_search() + { + if (_M_flags & regex_constants::match_continuous) + return _M_search_from_first(); + auto __cur = _M_begin; + do + { + _M_match_mode = false; + _M_init(__cur); + if (_M_main()) + return true; + } + // Continue when __cur == _M_end + while (__cur++ != _M_end); + return false; + } + + bool + _M_is_word(_CharT __ch) const + { + static const _CharT __s = 'w'; + return _M_re._M_traits.isctype + (__ch, _M_re._M_traits.lookup_classname(&__s, &__s+1)); + } + + bool + _M_at_begin() const + { + return _M_current == _M_begin + && !(_M_flags & (regex_constants::match_not_bol + | regex_constants::match_prev_avail)); + } + + bool + _M_at_end() const + { + return _M_current == _M_end + && !(_M_flags & regex_constants::match_not_eol); + } + + bool + _M_word_boundry(_State<_CharT, _TraitsT> __state) const; + + bool + _M_lookahead(_State<_CharT, _TraitsT> __state) const; + + public: + virtual void + _M_init(_BiIter __cur) = 0; + + virtual void + _M_set_start(_StateIdT __start) = 0; + + virtual bool + _M_main() = 0; + + _BiIter _M_current; + const _BiIter _M_begin; + const _BiIter _M_end; + const _RegexT& _M_re; + _ResultsT& _M_results; + const _FlagT _M_flags; + bool _M_match_mode; }; // A _DFSExecutor perform a DFS on given NFA and input string. At the very @@ -115,37 +184,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { public: typedef _Executor<_BiIter, _Alloc, _CharT, _TraitsT> _BaseT; - typedef _NFA<_CharT, _TraitsT> _RegexT; + typedef _NFA<_CharT, _TraitsT> _NFAT; + typedef typename _BaseT::_RegexT _RegexT; typedef typename _BaseT::_ResultsT _ResultsT; typedef typename _BaseT::_ResultsVec _ResultsVec; - typedef regex_constants::match_flag_type _FlagT; + typedef typename _BaseT::_FlagT _FlagT; + public: _DFSExecutor(_BiIter __begin, _BiIter __end, _ResultsT& __results, - const _RegexT& __nfa, - const _TraitsT& __traits, + const _RegexT& __re, _FlagT __flags) - : _BaseT(__begin, __end, __results, __flags, __nfa._M_sub_count()), - _M_traits(__traits), _M_nfa(__nfa), _M_results_ret(this->_M_results) + : _BaseT(__begin, __end, __results, __re, __flags), + _M_nfa(*std::static_pointer_cast<_NFA<_CharT, _TraitsT>> + (__re._M_automaton)), + _M_start_state(_M_nfa._M_start()) { } + private: void - _M_match() - { _M_dfs<true>(_M_nfa._M_start()); } + _M_init(_BiIter __cur) + { + _M_cur_results.resize(_M_nfa._M_sub_count() + 2); + this->_M_current = __cur; + } void - _M_search_from_first() - { _M_dfs<false>(_M_nfa._M_start()); } + _M_set_start(_StateIdT __start) + { _M_start_state = __start; } - private: - template<bool __match_mode> - bool - _M_dfs(_StateIdT __i); + bool + _M_main() + { return _M_dfs(this->_M_start_state); } + + bool + _M_dfs(_StateIdT __start); - _ResultsVec _M_results_ret; - const _TraitsT& _M_traits; - const _RegexT& _M_nfa; + // To record current solution. + _ResultsVec _M_cur_results; + const _NFAT& _M_nfa; + _StateIdT _M_start_state; }; // Like the DFS approach, it try every possible state transition; Unlike DFS, @@ -168,38 +247,114 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { public: typedef _Executor<_BiIter, _Alloc, _CharT, _TraitsT> _BaseT; - typedef _NFA<_CharT, _TraitsT> _RegexT; + typedef _NFA<_CharT, _TraitsT> _NFAT; + typedef typename _BaseT::_RegexT _RegexT; typedef typename _BaseT::_ResultsT _ResultsT; typedef typename _BaseT::_ResultsVec _ResultsVec; - typedef std::unique_ptr<_ResultsVec> _ResultsPtr; - typedef regex_constants::match_flag_type _FlagT; - - _BFSExecutor(_BiIter __begin, - _BiIter __end, - _ResultsT& __results, - const _RegexT& __nfa, - _FlagT __flags) - : _BaseT(__begin, __end, __results, __flags, __nfa._M_sub_count()), - _M_nfa(__nfa) + typedef typename _BaseT::_FlagT _FlagT; + // Here's a solution for greedy/ungreedy mode in BFS approach. We need to + // carefully work out how to compare to conflict matching states. + // + // A matching state is a pair(where, when); `where` is a NFA node; `when` + // is a _BiIter, indicating which char is the next to be matched. Two + // matching states conflict if they have equivalent `where` and `when`. + // + // Now we need to drop one and keep another, because at most one of them + // could be the final optimal solution. This behavior is affected by + // greedy policy. + // + // The definition of `greedy`: + // For the sequence of quantifiers in NFA sorted by there start position, + // now maintain a vector in every matching state, with equal length to + // quantifier seq, recording repeating times of every quantifier. Now to + // compare two matching states, we just lexically compare these two + // vectors. To win the compare(to survive), one matching state needs to + // make its greedy quantifier count larger, and ungreedy quantifiers + // count smaller. + // + // In the implementation, we recorded negtive counts for greedy + // quantifiers and positive counts of ungreedy ones. Now the implicit + // operator<() for lexicographical_compare will emit the answer. + // + // When two vectors equal, it means the `where`, `when` and quantifier + // counts are identical, and indicates the same solution; so just return + // false. + struct _ResultsEntry + : private _ResultsVec { - if (_M_nfa._M_start() != _S_invalid_state_id) - _M_covered[_M_nfa._M_start()] = - _ResultsPtr(new _ResultsVec(this->_M_results)); - _M_e_closure(); - } + public: + _ResultsEntry(unsigned int __res_sz, unsigned int __sz) + : _ResultsVec(__res_sz), _M_quant_keys(__sz) + { } + + void + resize(unsigned int __n) + { _ResultsVec::resize(__n); } + + unsigned int + size() + { return _ResultsVec::size(); } + + sub_match<_BiIter>& + operator[](unsigned int __idx) + { return _ResultsVec::operator[](__idx); } + + bool + operator<(const _ResultsEntry& __rhs) const + { + _GLIBCXX_DEBUG_ASSERT(_M_quant_keys.size() + == __rhs._M_quant_keys.size()); + return lexicographical_compare(_M_quant_keys.begin(), + _M_quant_keys.end(), + __rhs._M_quant_keys.begin(), + __rhs._M_quant_keys.end()); + } + + void + _M_inc(unsigned int __idx, bool __neg) + { _M_quant_keys[__idx] += __neg ? 1 : -1; } + + _ResultsVec + _M_get() + { return *this; } + + public: + std::vector<int> _M_quant_keys; + }; + typedef std::unique_ptr<_ResultsEntry> _ResultsPtr; + + public: + _BFSExecutor(_BiIter __begin, + _BiIter __end, + _ResultsT& __results, + const _RegexT& __re, + _FlagT __flags) + : _BaseT(__begin, __end, __results, __re, __flags), + _M_nfa(*std::static_pointer_cast<_NFA<_CharT, _TraitsT>> + (__re._M_automaton)), + _M_start_state(_M_nfa._M_start()) + { } + private: void - _M_match() - { _M_main_loop<true>(); } + _M_init(_BiIter __cur) + { + _GLIBCXX_DEBUG_ASSERT(this->_M_start_state != _S_invalid_state_id); + this->_M_current = __cur; + _M_covered.clear(); + _ResultsVec& __res(this->_M_results); + _M_covered[this->_M_start_state] = + _ResultsPtr(new _ResultsEntry(__res.size(), + _M_nfa._M_quant_count)); + _M_e_closure(); + } void - _M_search_from_first() - { _M_main_loop<false>(); } + _M_set_start(_StateIdT __start) + { _M_start_state = __start; } - private: - template<bool __match_mode> - void - _M_main_loop(); + bool + _M_main(); void _M_e_closure(); @@ -208,15 +363,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_move(); bool - _M_match_less_than(const _ResultsVec& __u, const _ResultsVec& __v) const; + _M_includes_some(); - bool - _M_includes_some() const; - - std::map<_StateIdT, _ResultsPtr> _M_covered; - const _RegexT& _M_nfa; + std::map<_StateIdT, _ResultsPtr> _M_covered; + // To record global optimal solution. + _ResultsPtr _M_cur_results; + const _NFAT& _M_nfa; + _StateIdT _M_start_state; }; + template<typename _BiIter, typename _Alloc, + typename _CharT, typename _TraitsT> + std::unique_ptr<_Executor<_BiIter, _Alloc, _CharT, _TraitsT>> + __get_executor(_BiIter __b, + _BiIter __e, + match_results<_BiIter, _Alloc>& __m, + const basic_regex<_CharT, _TraitsT>& __re, + regex_constants::match_flag_type __flags); + //@} regex-detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace __detail diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc index 788d65e54de..af2455b8a4e 100644 --- a/libstdc++-v3/include/bits/regex_executor.tcc +++ b/libstdc++-v3/include/bits/regex_executor.tcc @@ -36,7 +36,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _BiIter, typename _Alloc, typename _CharT, typename _TraitsT> - template<bool __match_mode> bool _DFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: _M_dfs(_StateIdT __i) { @@ -44,90 +43,122 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // This is not that certain. Need deeper investigate. return false; auto& __current = this->_M_current; - auto& __end = this->_M_end; - auto& __results = _M_results_ret; const auto& __state = _M_nfa[__i]; bool __ret = false; switch (__state._M_opcode) { case _S_opcode_alternative: - // Greedy mode by default. For non-greedy mode, - // swap _M_alt and _M_next. - // TODO: Add greedy mode option. - __ret = _M_dfs<__match_mode>(__state._M_alt) - || _M_dfs<__match_mode>(__state._M_next); + // Greedy or not, this is a question ;) + if (!__state._M_neg) + __ret = _M_dfs(__state._M_alt) + || _M_dfs(__state._M_next); + else + __ret = _M_dfs(__state._M_next) + || _M_dfs(__state._M_alt); break; case _S_opcode_subexpr_begin: // Here's the critical part: if there's nothing changed since last // visit, do NOT continue. This prevents the executor from get into // infinite loop when use "()*" to match "". // - // Every change on __results will be roll back after the recursion - // step finished. - if (!__results[__state._M_subexpr].matched - || __results[__state._M_subexpr].first != __current) + // Every change on _M_cur_results will be roll back after the + // recursion step finished. + if (!_M_cur_results[__state._M_subexpr].matched + || _M_cur_results[__state._M_subexpr].first != __current) { auto __back = __current; - __results[__state._M_subexpr].first = __current; - __ret = _M_dfs<__match_mode>(__state._M_next); - __results[__state._M_subexpr].first = __back; + _M_cur_results[__state._M_subexpr].first = __current; + __ret = _M_dfs(__state._M_next); + _M_cur_results[__state._M_subexpr].first = __back; } break; case _S_opcode_subexpr_end: - if (__results[__state._M_subexpr].second != __current - || __results[__state._M_subexpr].matched != true) + if (_M_cur_results[__state._M_subexpr].second != __current + || _M_cur_results[__state._M_subexpr].matched != true) { - auto __back = __results[__state._M_subexpr]; - __results[__state._M_subexpr].second = __current; - __results[__state._M_subexpr].matched = true; - __ret = _M_dfs<__match_mode>(__state._M_next); - __results[__state._M_subexpr] = __back; + auto __back = _M_cur_results[__state._M_subexpr]; + _M_cur_results[__state._M_subexpr].second = __current; + _M_cur_results[__state._M_subexpr].matched = true; + __ret = _M_dfs(__state._M_next); + _M_cur_results[__state._M_subexpr] = __back; } else - __ret = _M_dfs<__match_mode>(__state._M_next); + __ret = _M_dfs(__state._M_next); + break; + case _S_opcode_line_begin_assertion: + if (this->_M_at_begin()) + __ret = _M_dfs(__state._M_next); + break; + case _S_opcode_line_end_assertion: + if (this->_M_at_end()) + __ret = _M_dfs(__state._M_next); + break; + case _S_opcode_word_boundry: + if (this->_M_word_boundry(__state) == !__state._M_neg) + __ret = _M_dfs(__state._M_next); + break; + // Here __state._M_alt offers a single start node for a sub-NFA. + // We recursivly invoke our algorithm to match the sub-NFA. + case _S_opcode_subexpr_lookahead: + if (this->_M_lookahead(__state) == !__state._M_neg) + __ret = _M_dfs(__state._M_next); break; case _S_opcode_match: - if (__current != __end && __state._M_matches(*__current)) + if (__current != this->_M_end && __state._M_matches(*__current)) { ++__current; - __ret = _M_dfs<__match_mode>(__state._M_next); + __ret = _M_dfs(__state._M_next); --__current; } break; - // First fetch the matched result from __results as __submatch; + // First fetch the matched result from _M_cur_results as __submatch; // then compare it with // (__current, __current + (__submatch.second - __submatch.first)) // If matched, keep going; else just return to try another state. case _S_opcode_backref: { - auto& __submatch = __results[__state._M_backref_index]; + auto& __submatch = _M_cur_results[__state._M_backref_index]; if (!__submatch.matched) break; auto __last = __current; for (auto __tmp = __submatch.first; - __last != __end && __tmp != __submatch.second; + __last != this->_M_end && __tmp != __submatch.second; ++__tmp) ++__last; - if (_M_traits.transform(__submatch.first, __submatch.second) - == _M_traits.transform(__current, __last)) + if (this->_M_re._M_traits.transform(__submatch.first, + __submatch.second) + == this->_M_re._M_traits.transform(__current, __last)) if (__last != __current) { auto __backup = __current; __current = __last; - __ret = _M_dfs<__match_mode>(__state._M_next); + __ret = _M_dfs(__state._M_next); __current = __backup; } else - __ret = _M_dfs<__match_mode>(__state._M_next); + __ret = _M_dfs(__state._M_next); } break; case _S_opcode_accept: - if (__match_mode) - __ret = __current == __end; + if (this->_M_match_mode) + __ret = __current == this->_M_end; else __ret = true; + if (__current == this->_M_begin + && (this->_M_flags & regex_constants::match_not_null)) + __ret = false; if (__ret) - this->_M_results = __results; + { + _ResultsVec& __res(this->_M_results); + if (this->_M_re.flags() & regex_constants::nosubs) + { + _M_cur_results.resize(3); // truncate + __res.resize(3); + } + for (unsigned int __i = 0; __i < _M_cur_results.size(); ++__i) + if (_M_cur_results[__i].matched) + __res[__i] = _M_cur_results[__i]; + } break; default: _GLIBCXX_DEBUG_ASSERT(false); @@ -137,20 +168,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _BiIter, typename _Alloc, typename _CharT, typename _TraitsT> - template<bool __match_mode> - void _BFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: - _M_main_loop() + bool _BFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: + _M_main() { + bool __ret = false; + if (!this->_M_match_mode + && !(this->_M_flags & regex_constants::match_not_null)) + __ret = _M_includes_some() || __ret; while (this->_M_current != this->_M_end) { - if (!__match_mode) - if (_M_includes_some()) - return; _M_move(); ++this->_M_current; _M_e_closure(); + if (!this->_M_match_mode) + // To keep regex_search greedy, no "return true" here. + __ret = _M_includes_some() || __ret; } - _M_includes_some(); + if (this->_M_match_mode) + __ret = _M_includes_some(); + if (__ret) + { + _ResultsVec& __res(this->_M_results); + if (this->_M_re.flags() & regex_constants::nosubs) + { + // truncate + _M_cur_results->resize(3); + __res.resize(3); + } + for (unsigned int __i = 0; __i < _M_cur_results->size(); ++__i) + if ((*_M_cur_results)[__i].matched) + __res[__i] = (*_M_cur_results)[__i]; + } + return __ret; } template<typename _BiIter, typename _Alloc, @@ -158,9 +207,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _BFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: _M_e_closure() { - auto& __current = this->_M_current; std::queue<_StateIdT> __q; std::vector<bool> __in_q(_M_nfa.size(), false); + auto& __current = this->_M_current; + for (auto& __it : _M_covered) { __in_q[__it.first] = true; @@ -173,18 +223,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __in_q[__u] = false; const auto& __state = _M_nfa[__u]; - // Can be implemented using method, but there're too much arguments. - // I would use macro function before C++11, but lambda is a better - // choice, since hopefully compiler can inline it. + // Can be implemented using method, but there will be too many + // arguments. I would use macro function before C++11, but lambda is + // a better choice, since hopefully compiler can inline it. auto __add_visited_state = [&](_StateIdT __v) { if (__v == _S_invalid_state_id) return; if (_M_covered.count(__u) != 0 && (_M_covered.count(__v) == 0 - || _M_match_less_than(*_M_covered[__u], *_M_covered[__v]))) + || *_M_covered[__u] < *_M_covered[__v])) { - _M_covered[__v] = _ResultsPtr(new _ResultsVec(*_M_covered[__u])); + _M_covered[__v] = + _ResultsPtr(new _ResultsEntry(*_M_covered[__u])); // if a state is updated, it's outgoing neighbors should be // reconsidered too. Push them to the queue. if (!__in_q[__v]) @@ -195,19 +246,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + // Identical to DFS's switch part. switch (__state._M_opcode) { + // Needs to maintain quantifier count vector here. A quantifier + // must be concerned with a alt node. case _S_opcode_alternative: - __add_visited_state(__state._M_next); - __add_visited_state(__state._M_alt); + { + __add_visited_state(__state._M_next); + auto __back = + _M_covered[__u]->_M_quant_keys[__state._M_quant_index]; + _M_covered[__u]->_M_inc(__state._M_quant_index, + __state._M_neg); + __add_visited_state(__state._M_alt); + _M_covered[__u]->_M_quant_keys[__state._M_quant_index] + = __back; + } break; case _S_opcode_subexpr_begin: { - auto& __cu = *_M_covered[__u]; - auto __back = __cu[__state._M_subexpr].first; - __cu[__state._M_subexpr].first = __current; - __add_visited_state(__state._M_next); - __cu[__state._M_subexpr].first = __back; + auto& __sub = (*_M_covered[__u])[__state._M_subexpr]; + if (!__sub.matched || __sub.first != __current) + { + auto __back = __sub.first; + __sub.first = __current; + __add_visited_state(__state._M_next); + __sub.first = __back; + } } break; case _S_opcode_subexpr_end: @@ -220,10 +285,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __cu[__state._M_subexpr] = __back; } break; + case _S_opcode_line_begin_assertion: + if (this->_M_at_begin()) + __add_visited_state(__state._M_next); + break; + case _S_opcode_line_end_assertion: + if (this->_M_at_end()) + __add_visited_state(__state._M_next); + break; + case _S_opcode_word_boundry: + if (this->_M_word_boundry(__state) == !__state._M_neg) + __add_visited_state(__state._M_next); + break; + case _S_opcode_subexpr_lookahead: + if (this->_M_lookahead(__state) == !__state._M_neg) + __add_visited_state(__state._M_next); + break; case _S_opcode_match: break; case _S_opcode_accept: - __add_visited_state(__state._M_next); break; default: _GLIBCXX_DEBUG_ASSERT(false); @@ -244,7 +324,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION && __state._M_matches(*this->_M_current)) if (__state._M_next != _S_invalid_state_id) if (__next.count(__state._M_next) == 0 - || _M_match_less_than(*__it.second, *__next[__state._M_next])) + || *__it.second < *__next[__state._M_next]) __next[__state._M_next] = move(__it.second); } _M_covered = move(__next); @@ -253,37 +333,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _BiIter, typename _Alloc, typename _CharT, typename _TraitsT> bool _BFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: - _M_match_less_than(const _ResultsVec& __u, const _ResultsVec& __v) const - { - // TODO: Greedy and Non-greedy support - _GLIBCXX_DEBUG_ASSERT(__u.size() == __v.size()); - auto __size = __u.size(); - for (auto __i = 0; __i < __size; __i++) - { - auto __uit = __u[__i], __vit = __v[__i]; - if (__uit.matched && !__vit.matched) - return true; - if (!__uit.matched && __vit.matched) - return false; - if (__uit.matched && __vit.matched) - { - // GREEDY - if (__uit.first != __vit.first) - return __uit.first < __vit.first; - if (__uit.second != __vit.second) - return __uit.second > __vit.second; - } - } - return false; - } - - template<typename _BiIter, typename _Alloc, - typename _CharT, typename _TraitsT> - bool _BFSExecutor<_BiIter, _Alloc, _CharT, _TraitsT>:: - _M_includes_some() const + _M_includes_some() { auto& __s = _M_nfa._M_final_states(); auto& __t = _M_covered; + bool __succ = false; if (__s.size() > 0 && __t.size() > 0) { auto __first = __s.begin(); @@ -292,16 +346,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { if (*__first < __second->first) ++__first; - else if (__second->first < *__first) + else if (*__first > __second->first) ++__second; else { - this->_M_results = *__second->second; - return true; + if (_M_cur_results == nullptr + || *__second->second < *_M_cur_results) + _M_cur_results = + _ResultsPtr(new _ResultsEntry(*__second->second)); + __succ = true; + ++__first; + ++__second; } } } - return false; + return __succ; + } + + // Return whether now is at some word boundry. + template<typename _BiIter, typename _Alloc, + typename _CharT, typename _TraitsT> + bool _Executor<_BiIter, _Alloc, _CharT, _TraitsT>:: + _M_word_boundry(_State<_CharT, _TraitsT> __state) const + { + // By definition. + bool __ans = false; + auto __pre = _M_current; + --__pre; + if (!(_M_at_begin() && _M_at_end())) + if (_M_at_begin()) + __ans = _M_is_word(*_M_current) + && !(_M_flags & regex_constants::match_not_bow); + else if (_M_at_end()) + __ans = _M_is_word(*__pre) + && !(_M_flags & regex_constants::match_not_eow); + else + __ans = _M_is_word(*_M_current) + != _M_is_word(*__pre); + return __ans; + } + + // Return whether now match the given sub-NFA. + template<typename _BiIter, typename _Alloc, + typename _CharT, typename _TraitsT> + bool _Executor<_BiIter, _Alloc, _CharT, _TraitsT>:: + _M_lookahead(_State<_CharT, _TraitsT> __state) const + { + auto __sub = __get_executor(this->_M_current, + this->_M_end, + this->_M_results, + this->_M_re, + this->_M_flags); + __sub->_M_set_start(__state._M_alt); + return __sub->_M_search_from_first(); } template<typename _BiIter, typename _Alloc, @@ -320,9 +417,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto __p = std::static_pointer_cast<_NFA<_CharT, _TraitsT>> (__re._M_automaton); if (__p->_M_has_backref) - return _ExecutorPtr(new _DFSExecutorT(__b, __e, __m, *__p, - __re._M_traits, __flags)); - return _ExecutorPtr(new _BFSExecutorT(__b, __e, __m, *__p, __flags)); + return _ExecutorPtr(new _DFSExecutorT(__b, __e, __m, __re, __flags)); + return _ExecutorPtr(new _BFSExecutorT(__b, __e, __m, __re, __flags)); } _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/regex_scanner.h b/libstdc++-v3/include/bits/regex_scanner.h index 080ef635b0c..09a18f634a0 100644 --- a/libstdc++-v3/include/bits/regex_scanner.h +++ b/libstdc++-v3/include/bits/regex_scanner.h @@ -68,8 +68,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _S_token_backref, _S_token_subexpr_begin, _S_token_subexpr_no_group_begin, - _S_token_subexpr_lookahead_begin, - _S_token_subexpr_neg_lookahead_begin, + _S_token_subexpr_lookahead_begin, // neg if _M_value[0] == 'n' _S_token_subexpr_end, _S_token_bracket_begin, _S_token_bracket_neg_begin, @@ -84,8 +83,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _S_token_or, _S_token_closure0, _S_token_closure1, + _S_token_ungreedy, _S_token_line_begin, _S_token_line_end, + _S_token_word_bound, // neg if _M_value[0] == 'n' _S_token_comma, _S_token_dup_count, _S_token_eof, @@ -173,7 +174,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _StringT _M_value; bool _M_at_bracket_start; public: - // TODO: make them static when this file is stable. + // FIXME: make them static when this file is stable. const std::map<char, _TokenT> _M_token_map; const std::map<char, char> _M_ecma_escape_map; const std::map<char, char> _M_awk_escape_map; diff --git a/libstdc++-v3/include/bits/regex_scanner.tcc b/libstdc++-v3/include/bits/regex_scanner.tcc index 0d1d2cd9778..abdbcc64f1f 100644 --- a/libstdc++-v3/include/bits/regex_scanner.tcc +++ b/libstdc++-v3/include/bits/regex_scanner.tcc @@ -28,7 +28,7 @@ * Do not attempt to use it directly. @headername{regex} */ -// TODO make comments doxygen format +// FIXME make comments doxygen format. // N3376 specified 6 regex styles: ECMAScript, basic, extended, grep, egrep // and awk @@ -210,11 +210,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { ++_M_current; _M_token = _S_token_subexpr_lookahead_begin; + _M_value.assign(1, 'p'); } else if (*_M_current == '!') { ++_M_current; - _M_token = _S_token_subexpr_neg_lookahead_begin; + _M_token = _S_token_subexpr_lookahead_begin; + _M_value.assign(1, 'n'); } else __throw_regex_error(regex_constants::error_paren); @@ -370,10 +372,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_token = _S_token_ord_char; _M_value.assign(1, _M_escape_map.at(__c)); } + else if (__c == 'b') + { + _M_token = _S_token_word_bound; + _M_value.assign(1, 'p'); + } + else if (__c == 'B') + { + _M_token = _S_token_word_bound; + _M_value.assign(1, 'n'); + } // N3376 28.13 - else if (__c == 'b' - || __c == 'B' - || __c == 'd' + else if (__c == 'd' || __c == 'D' || __c == 's' || __c == 'S' @@ -579,9 +589,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION case _S_token_subexpr_lookahead_begin: ostr << "lookahead subexpr begin\n"; break; - case _S_token_subexpr_neg_lookahead_begin: - ostr << "neg lookahead subexpr begin\n"; - break; case _S_token_subexpr_end: ostr << "subexpr end\n"; break; diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 9d6b466cf2e..b06211e0100 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -385,38 +385,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _DistanceType; _DistanceType __tailSize = __last - __first; - const _DistanceType __pattSize = __count; + _DistanceType __remainder = __count; - if (__tailSize < __pattSize) - return __last; - - const _DistanceType __skipOffset = __pattSize - 1; - _RandomAccessIter __lookAhead = __first + __skipOffset; - __tailSize -= __pattSize; - - while (1) // the main loop... + while (__remainder <= __tailSize) // the main loop... { - // __lookAhead here is always pointing to the last element of next - // possible match. - while (!(*__lookAhead == __val)) // the skip loop... - { - if (__tailSize < __pattSize) - return __last; // Failure - __lookAhead += __pattSize; - __tailSize -= __pattSize; - } - _DistanceType __remainder = __skipOffset; - for (_RandomAccessIter __backTrack = __lookAhead - 1; - *__backTrack == __val; --__backTrack) + __first += __remainder; + __tailSize -= __remainder; + // __first here is always pointing to one past the last element of + // next possible match. + _RandomAccessIter __backTrack = __first; + while (*--__backTrack == __val) { if (--__remainder == 0) - return (__lookAhead - __skipOffset); // Success + return (__first - __count); // Success } - if (__remainder > __tailSize) - return __last; // Failure - __lookAhead += __remainder; - __tailSize -= __remainder; + __remainder = __count + 1 - (__first - __backTrack); } + return __last; // Failure } // search_n @@ -478,38 +463,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _DistanceType; _DistanceType __tailSize = __last - __first; - const _DistanceType __pattSize = __count; + _DistanceType __remainder = __count; - if (__tailSize < __pattSize) - return __last; - - const _DistanceType __skipOffset = __pattSize - 1; - _RandomAccessIter __lookAhead = __first + __skipOffset; - __tailSize -= __pattSize; - - while (1) // the main loop... + while (__remainder <= __tailSize) // the main loop... { - // __lookAhead here is always pointing to the last element of next - // possible match. - while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop... - { - if (__tailSize < __pattSize) - return __last; // Failure - __lookAhead += __pattSize; - __tailSize -= __pattSize; - } - _DistanceType __remainder = __skipOffset; - for (_RandomAccessIter __backTrack = __lookAhead - 1; - __binary_pred(*__backTrack, __val); --__backTrack) + __first += __remainder; + __tailSize -= __remainder; + // __first here is always pointing to one past the last element of + // next possible match. + _RandomAccessIter __backTrack = __first; + while (__binary_pred(*--__backTrack, __val)) { if (--__remainder == 0) - return (__lookAhead - __skipOffset); // Success + return (__first - __count); // Success } - if (__remainder > __tailSize) - return __last; // Failure - __lookAhead += __remainder; - __tailSize -= __remainder; + __remainder = __count + 1 - (__first - __backTrack); } + return __last; // Failure } // find_end for forward iterators. diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index e1daac2ddda..1c889356460 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -611,7 +611,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * loop count will be known (and therefore a candidate for compiler * optimizations such as unrolling). * - * Result may not be in the range [first,last). Use copy instead. Note + * Result may not be in the range (first,last]. Use copy instead. Note * that the start of the output range may overlap [first,last). */ template<typename _BI1, typename _BI2> diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index a4656734469..98556f59848 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -108,7 +108,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - static size_t _S_buffer_size() + static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT { return __deque_buf_size(sizeof(_Tp)); } typedef std::random_access_iterator_tag iterator_category; @@ -125,31 +125,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Tp* _M_last; _Map_pointer _M_node; - _Deque_iterator(_Tp* __x, _Map_pointer __y) + _Deque_iterator(_Tp* __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT : _M_cur(__x), _M_first(*__y), _M_last(*__y + _S_buffer_size()), _M_node(__y) { } - _Deque_iterator() + _Deque_iterator() _GLIBCXX_NOEXCEPT : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { } - _Deque_iterator(const iterator& __x) + _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT : _M_cur(__x._M_cur), _M_first(__x._M_first), _M_last(__x._M_last), _M_node(__x._M_node) { } iterator - _M_const_cast() const + _M_const_cast() const _GLIBCXX_NOEXCEPT { return iterator(_M_cur, _M_node); } reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return *_M_cur; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return _M_cur; } _Self& - operator++() + operator++() _GLIBCXX_NOEXCEPT { ++_M_cur; if (_M_cur == _M_last) @@ -161,7 +161,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; ++*this; @@ -169,7 +169,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self& - operator--() + operator--() _GLIBCXX_NOEXCEPT { if (_M_cur == _M_first) { @@ -181,7 +181,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; --*this; @@ -189,7 +189,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self& - operator+=(difference_type __n) + operator+=(difference_type __n) _GLIBCXX_NOEXCEPT { const difference_type __offset = __n + (_M_cur - _M_first); if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) @@ -208,25 +208,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self - operator+(difference_type __n) const + operator+(difference_type __n) const _GLIBCXX_NOEXCEPT { _Self __tmp = *this; return __tmp += __n; } _Self& - operator-=(difference_type __n) + operator-=(difference_type __n) _GLIBCXX_NOEXCEPT { return *this += -__n; } _Self - operator-(difference_type __n) const + operator-(difference_type __n) const _GLIBCXX_NOEXCEPT { _Self __tmp = *this; return __tmp -= __n; } reference - operator[](difference_type __n) const + operator[](difference_type __n) const _GLIBCXX_NOEXCEPT { return *(*this + __n); } /** @@ -235,7 +235,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * immediately afterwards, based on _M_first and _M_last. */ void - _M_set_node(_Map_pointer __new_node) + _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT { _M_node = __new_node; _M_first = *__new_node; @@ -249,33 +249,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return __x._M_cur == __y._M_cur; } template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline bool operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return __x._M_cur == __y._M_cur; } template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return !(__x == __y); } template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline bool operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return !(__x == __y); } template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); } @@ -283,47 +283,47 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename _RefR, typename _PtrR> inline bool operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node); } template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return __y < __x; } template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline bool operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return __y < __x; } template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return !(__y < __x); } template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline bool operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return !(__y < __x); } template<typename _Tp, typename _Ref, typename _Ptr> inline bool operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return !(__x < __y); } template<typename _Tp, typename _RefL, typename _PtrL, typename _RefR, typename _PtrR> inline bool operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return !(__x < __y); } // _GLIBCXX_RESOLVE_LIB_DEFECTS @@ -333,7 +333,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Ref, typename _Ptr> inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x, - const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) + const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT { return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size()) @@ -345,7 +345,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename _RefR, typename _PtrR> inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x, - const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) + const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT { return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) @@ -356,6 +356,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Ref, typename _Ptr> inline _Deque_iterator<_Tp, _Ref, _Ptr> operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) + _GLIBCXX_NOEXCEPT { return __x + __n; } template<typename _Tp> @@ -466,7 +467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Deque_base(const allocator_type& __a) : _M_impl(__a) - { } + { _M_initialize_map(0); } #if __cplusplus >= 201103L _Deque_base(_Deque_base&& __x) @@ -483,7 +484,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif - ~_Deque_base(); + ~_Deque_base() _GLIBCXX_NOEXCEPT; protected: //This struct encapsulates the implementation of the std::deque @@ -506,13 +507,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_start(), _M_finish() { } - _Deque_impl(const _Tp_alloc_type& __a) + _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish() { } #if __cplusplus >= 201103L - _Deque_impl(_Tp_alloc_type&& __a) + _Deque_impl(_Tp_alloc_type&& __a) _GLIBCXX_NOEXCEPT : _Tp_alloc_type(std::move(__a)), _M_map(0), _M_map_size(0), _M_start(), _M_finish() { } @@ -538,7 +539,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } void - _M_deallocate_node(_Tp* __p) + _M_deallocate_node(_Tp* __p) _GLIBCXX_NOEXCEPT { _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } @@ -548,13 +549,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_get_map_allocator().allocate(__n); } void - _M_deallocate_map(_Tp** __p, size_t __n) + _M_deallocate_map(_Tp** __p, size_t __n) _GLIBCXX_NOEXCEPT { _M_get_map_allocator().deallocate(__p, __n); } protected: void _M_initialize_map(size_t); void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish); - void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish); + void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) _GLIBCXX_NOEXCEPT; enum { _S_initial_map_size = 8 }; _Deque_impl _M_impl; @@ -562,7 +563,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> _Deque_base<_Tp, _Alloc>:: - ~_Deque_base() + ~_Deque_base() _GLIBCXX_NOEXCEPT { if (this->_M_impl._M_map) { @@ -640,7 +641,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> void _Deque_base<_Tp, _Alloc>:: - _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) + _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) _GLIBCXX_NOEXCEPT { for (_Tp** __n = __nstart; __n < __nfinish; ++__n) _M_deallocate_node(*__n); @@ -758,7 +759,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER protected: typedef pointer* _Map_pointer; - static size_t _S_buffer_size() + static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT { return __deque_buf_size(sizeof(_Tp)); } // Functions controlling memory layout, and nothing else. @@ -781,18 +782,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // [23.2.1.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) /** - * @brief Default constructor creates no elements. - */ - deque() - : _Base() { } - - /** * @brief Creates a %deque with no elements. * @param __a An allocator object. */ explicit - deque(const allocator_type& __a) - : _Base(__a, 0) { } + deque(const allocator_type& __a = allocator_type()) + : _Base(__a) { } #if __cplusplus >= 201103L /** @@ -940,7 +935,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * @a __x is a valid, but unspecified %deque. */ deque& - operator=(deque&& __x) + operator=(deque&& __x) noexcept { // NB: DR 1204. // NB: DR 675. @@ -1220,7 +1215,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #if __cplusplus >= 201103L /** A non-binding request to reduce memory use. */ void - shrink_to_fit() + shrink_to_fit() noexcept { _M_shrink_to_fit(); } #endif @@ -1245,7 +1240,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * see at().) */ reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { return this->_M_impl._M_start[difference_type(__n)]; } /** @@ -1260,7 +1255,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * see at().) */ const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_start[difference_type(__n)]; } protected: @@ -1314,7 +1309,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %deque. */ reference - front() + front() _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -1322,7 +1317,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %deque. */ const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -1330,7 +1325,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * %deque. */ reference - back() + back() _GLIBCXX_NOEXCEPT { iterator __tmp = end(); --__tmp; @@ -1342,7 +1337,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %deque. */ const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { const_iterator __tmp = end(); --__tmp; @@ -1422,7 +1417,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * needed, it should be retrieved before pop_front() is called. */ void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1) @@ -1443,7 +1438,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * needed, it should be retrieved before pop_back() is called. */ void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first) @@ -1655,7 +1650,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * std::swap(d1,d2) will feed to this function. */ void - swap(deque& __x) + swap(deque& __x) _GLIBCXX_NOEXCEPT { std::swap(this->_M_impl._M_start, __x._M_impl._M_start); std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h index 9952c2c92d6..1f555a4ef28 100644 --- a/libstdc++-v3/include/bits/stl_iterator.h +++ b/libstdc++-v3/include/bits/stl_iterator.h @@ -721,22 +721,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef typename __traits_type::reference reference; typedef typename __traits_type::pointer pointer; - _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { } + _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT + : _M_current(_Iterator()) { } explicit - __normal_iterator(const _Iterator& __i) : _M_current(__i) { } + __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT + : _M_current(__i) { } // Allow iterator to const_iterator conversion template<typename _Iter> __normal_iterator(const __normal_iterator<_Iter, typename __enable_if< (std::__are_same<_Iter, typename _Container::pointer>::__value), - _Container>::__type>& __i) + _Container>::__type>& __i) _GLIBCXX_NOEXCEPT : _M_current(__i.base()) { } #if __cplusplus >= 201103L __normal_iterator<typename _Container::pointer, _Container> - _M_const_cast() const + _M_const_cast() const noexcept { using _PTraits = std::pointer_traits<typename _Container::pointer>; return __normal_iterator<typename _Container::pointer, _Container> @@ -751,59 +753,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Forward iterator requirements reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return *_M_current; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return _M_current; } __normal_iterator& - operator++() + operator++() _GLIBCXX_NOEXCEPT { ++_M_current; return *this; } __normal_iterator - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { return __normal_iterator(_M_current++); } // Bidirectional iterator requirements __normal_iterator& - operator--() + operator--() _GLIBCXX_NOEXCEPT { --_M_current; return *this; } __normal_iterator - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { return __normal_iterator(_M_current--); } // Random access iterator requirements reference - operator[](const difference_type& __n) const + operator[](difference_type __n) const _GLIBCXX_NOEXCEPT { return _M_current[__n]; } __normal_iterator& - operator+=(const difference_type& __n) + operator+=(difference_type __n) _GLIBCXX_NOEXCEPT { _M_current += __n; return *this; } __normal_iterator - operator+(const difference_type& __n) const + operator+(difference_type __n) const _GLIBCXX_NOEXCEPT { return __normal_iterator(_M_current + __n); } __normal_iterator& - operator-=(const difference_type& __n) + operator-=(difference_type __n) _GLIBCXX_NOEXCEPT { _M_current -= __n; return *this; } __normal_iterator - operator-(const difference_type& __n) const + operator-(difference_type __n) const _GLIBCXX_NOEXCEPT { return __normal_iterator(_M_current - __n); } const _Iterator& - base() const + base() const _GLIBCXX_NOEXCEPT { return _M_current; } }; @@ -820,24 +822,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline bool operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() == __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator==(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() == __rhs.base(); } template<typename _IteratorL, typename _IteratorR, typename _Container> inline bool operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() != __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() != __rhs.base(); } // Random access iterator requirements @@ -845,48 +851,56 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline bool operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() < __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator<(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() < __rhs.base(); } template<typename _IteratorL, typename _IteratorR, typename _Container> inline bool operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() > __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator>(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() > __rhs.base(); } template<typename _IteratorL, typename _IteratorR, typename _Container> inline bool operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() <= __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() <= __rhs.base(); } template<typename _IteratorL, typename _IteratorR, typename _Container> inline bool operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, const __normal_iterator<_IteratorR, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() >= __rhs.base(); } template<typename _Iterator, typename _Container> inline bool operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() >= __rhs.base(); } // _GLIBCXX_RESOLVE_LIB_DEFECTS @@ -898,7 +912,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // DR 685. inline auto operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, - const __normal_iterator<_IteratorR, _Container>& __rhs) + const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept -> decltype(__lhs.base() - __rhs.base()) #else inline typename __normal_iterator<_IteratorL, _Container>::difference_type @@ -911,12 +925,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline typename __normal_iterator<_Iterator, _Container>::difference_type operator-(const __normal_iterator<_Iterator, _Container>& __lhs, const __normal_iterator<_Iterator, _Container>& __rhs) + _GLIBCXX_NOEXCEPT { return __lhs.base() - __rhs.base(); } template<typename _Iterator, typename _Container> inline __normal_iterator<_Iterator, _Container> operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n, const __normal_iterator<_Iterator, _Container>& __i) + _GLIBCXX_NOEXCEPT { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 5e8312dc6ff..71ef819176c 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -133,35 +133,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef _Tp* pointer; typedef _Tp& reference; - _List_iterator() + _List_iterator() _GLIBCXX_NOEXCEPT : _M_node() { } explicit - _List_iterator(__detail::_List_node_base* __x) + _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT : _M_node(__x) { } _Self - _M_const_cast() const + _M_const_cast() const _GLIBCXX_NOEXCEPT { return *this; } // Must downcast from _List_node_base to _List_node to get to _M_data. reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return static_cast<_Node*>(_M_node)->_M_data; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } _Self& - operator++() + operator++() _GLIBCXX_NOEXCEPT { _M_node = _M_node->_M_next; return *this; } _Self - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _M_node->_M_next; @@ -169,14 +169,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self& - operator--() + operator--() _GLIBCXX_NOEXCEPT { _M_node = _M_node->_M_prev; return *this; } _Self - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _M_node->_M_prev; @@ -184,11 +184,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } bool - operator==(const _Self& __x) const + operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node == __x._M_node; } bool - operator!=(const _Self& __x) const + operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node != __x._M_node; } // The only member points to the %list element. @@ -213,39 +213,40 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef const _Tp* pointer; typedef const _Tp& reference; - _List_const_iterator() + _List_const_iterator() _GLIBCXX_NOEXCEPT : _M_node() { } explicit _List_const_iterator(const __detail::_List_node_base* __x) + _GLIBCXX_NOEXCEPT : _M_node(__x) { } - _List_const_iterator(const iterator& __x) + _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT : _M_node(__x._M_node) { } iterator - _M_const_cast() const + _M_const_cast() const _GLIBCXX_NOEXCEPT { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); } // Must downcast from List_node_base to _List_node to get to // _M_data. reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return static_cast<_Node*>(_M_node)->_M_data; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } _Self& - operator++() + operator++() _GLIBCXX_NOEXCEPT { _M_node = _M_node->_M_next; return *this; } _Self - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _M_node->_M_next; @@ -253,14 +254,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } _Self& - operator--() + operator--() _GLIBCXX_NOEXCEPT { _M_node = _M_node->_M_prev; return *this; } _Self - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _M_node->_M_prev; @@ -268,11 +269,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } bool - operator==(const _Self& __x) const + operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node == __x._M_node; } bool - operator!=(const _Self& __x) const + operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node != __x._M_node; } // The only member points to the %list element. @@ -282,13 +283,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Val> inline bool operator==(const _List_iterator<_Val>& __x, - const _List_const_iterator<_Val>& __y) + const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT { return __x._M_node == __y._M_node; } template<typename _Val> inline bool operator!=(const _List_iterator<_Val>& __x, - const _List_const_iterator<_Val>& __y) + const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT { return __x._M_node != __y._M_node; } @@ -324,12 +325,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER : _Node_alloc_type(), _M_node() { } - _List_impl(const _Node_alloc_type& __a) + _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT : _Node_alloc_type(__a), _M_node() { } #if __cplusplus >= 201103L - _List_impl(_Node_alloc_type&& __a) + _List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT : _Node_alloc_type(std::move(__a)), _M_node() { } #endif @@ -342,7 +343,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_impl._Node_alloc_type::allocate(1); } void - _M_put_node(_List_node<_Tp>* __p) + _M_put_node(_List_node<_Tp>* __p) _GLIBCXX_NOEXCEPT { _M_impl._Node_alloc_type::deallocate(__p, 1); } public: @@ -368,12 +369,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER : _M_impl() { _M_init(); } - _List_base(const _Node_alloc_type& __a) + _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT : _M_impl(__a) { _M_init(); } #if __cplusplus >= 201103L - _List_base(_List_base&& __x) + _List_base(_List_base&& __x) noexcept : _M_impl(std::move(__x._M_get_Node_allocator())) { _M_init(); @@ -386,10 +387,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_clear(); } void - _M_clear(); + _M_clear() _GLIBCXX_NOEXCEPT; void - _M_init() + _M_init() _GLIBCXX_NOEXCEPT { this->_M_impl._M_node._M_next = &this->_M_impl._M_node; this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; @@ -526,17 +527,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // [23.2.2.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) /** - * @brief Default constructor creates no elements. - */ - list() - : _Base() { } - - /** * @brief Creates a %list with no elements. * @param __a An allocator object. */ explicit - list(const allocator_type& __a) + list(const allocator_type& __a = allocator_type()) _GLIBCXX_NOEXCEPT : _Base(_Node_alloc_type(__a)) { } #if __cplusplus >= 201103L @@ -932,7 +927,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %list. */ reference - front() + front() _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -940,7 +935,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %list. */ const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -948,7 +943,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * of the %list. */ reference - back() + back() _GLIBCXX_NOEXCEPT { iterator __tmp = end(); --__tmp; @@ -960,7 +955,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %list. */ const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { const_iterator __tmp = end(); --__tmp; @@ -1006,7 +1001,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * called. */ void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { this->_M_erase(begin()); } /** @@ -1046,7 +1041,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * is needed, it should be retrieved before pop_back() is called. */ void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } #if __cplusplus >= 201103L @@ -1231,7 +1226,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ iterator #if __cplusplus >= 201103L - erase(const_iterator __position); + erase(const_iterator __position) noexcept; #else erase(iterator __position); #endif @@ -1256,7 +1251,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ iterator #if __cplusplus >= 201103L - erase(const_iterator __first, const_iterator __last) + erase(const_iterator __first, const_iterator __last) noexcept #else erase(iterator __first, iterator __last) #endif @@ -1314,7 +1309,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void #if __cplusplus >= 201103L - splice(const_iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) noexcept #else splice(iterator __position, list& __x) #endif @@ -1330,7 +1325,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #if __cplusplus >= 201103L void - splice(const_iterator __position, list& __x) + splice(const_iterator __position, list& __x) noexcept { splice(__position, std::move(__x)); } #endif @@ -1346,7 +1341,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * inserts it into the current list before @a __position. */ void - splice(const_iterator __position, list&& __x, const_iterator __i) + splice(const_iterator __position, list&& __x, const_iterator __i) noexcept #else /** * @brief Insert element from another %list. @@ -1385,7 +1380,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * inserts it into the current list before @a __position. */ void - splice(const_iterator __position, list& __x, const_iterator __i) + splice(const_iterator __position, list& __x, const_iterator __i) noexcept { splice(__position, std::move(__x), __i); } #endif @@ -1405,7 +1400,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void splice(const_iterator __position, list&& __x, const_iterator __first, - const_iterator __last) + const_iterator __last) noexcept #else /** * @brief Insert range from another %list. @@ -1451,7 +1446,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void splice(const_iterator __position, list& __x, const_iterator __first, - const_iterator __last) + const_iterator __last) noexcept { splice(__position, std::move(__x), __first, __last); } #endif @@ -1687,7 +1682,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Erases element at position given. void - _M_erase(iterator __position) + _M_erase(iterator __position) _GLIBCXX_NOEXCEPT { __position._M_node->_M_unhook(); _Node* __n = static_cast<_Node*>(__position._M_node); @@ -1701,11 +1696,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // To implement the splice (and merge) bits of N1599. void - _M_check_equal_allocators(list& __x) + _M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT { if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) - __throw_runtime_error(__N("list::_M_check_equal_allocators")); + __builtin_abort(); } }; diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 91bf4df4511..5ed3760633e 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -99,28 +99,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Base_ptr _M_right; static _Base_ptr - _S_minimum(_Base_ptr __x) + _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT { while (__x->_M_left != 0) __x = __x->_M_left; return __x; } static _Const_Base_ptr - _S_minimum(_Const_Base_ptr __x) + _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { while (__x->_M_left != 0) __x = __x->_M_left; return __x; } static _Base_ptr - _S_maximum(_Base_ptr __x) + _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT { while (__x->_M_right != 0) __x = __x->_M_right; return __x; } static _Const_Base_ptr - _S_maximum(_Const_Base_ptr __x) + _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { while (__x->_M_right != 0) __x = __x->_M_right; return __x; @@ -167,31 +167,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; typedef _Rb_tree_node<_Tp>* _Link_type; - _Rb_tree_iterator() + _Rb_tree_iterator() _GLIBCXX_NOEXCEPT : _M_node() { } explicit - _Rb_tree_iterator(_Link_type __x) + _Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT : _M_node(__x) { } reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(_M_node)->_M_value_field; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return std::__addressof(static_cast<_Link_type> (_M_node)->_M_value_field); } _Self& - operator++() + operator++() _GLIBCXX_NOEXCEPT { _M_node = _Rb_tree_increment(_M_node); return *this; } _Self - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _Rb_tree_increment(_M_node); @@ -199,14 +199,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } _Self& - operator--() + operator--() _GLIBCXX_NOEXCEPT { _M_node = _Rb_tree_decrement(_M_node); return *this; } _Self - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _Rb_tree_decrement(_M_node); @@ -214,11 +214,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } bool - operator==(const _Self& __x) const + operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node == __x._M_node; } bool - operator!=(const _Self& __x) const + operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node != __x._M_node; } _Base_ptr _M_node; @@ -240,39 +240,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; typedef const _Rb_tree_node<_Tp>* _Link_type; - _Rb_tree_const_iterator() + _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT : _M_node() { } explicit - _Rb_tree_const_iterator(_Link_type __x) + _Rb_tree_const_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT : _M_node(__x) { } - _Rb_tree_const_iterator(const iterator& __it) + _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT : _M_node(__it._M_node) { } iterator - _M_const_cast() const + _M_const_cast() const _GLIBCXX_NOEXCEPT { return iterator(static_cast<typename iterator::_Link_type> (const_cast<typename iterator::_Base_ptr>(_M_node))); } reference - operator*() const + operator*() const _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(_M_node)->_M_value_field; } pointer - operator->() const + operator->() const _GLIBCXX_NOEXCEPT { return std::__addressof(static_cast<_Link_type> (_M_node)->_M_value_field); } _Self& - operator++() + operator++() _GLIBCXX_NOEXCEPT { _M_node = _Rb_tree_increment(_M_node); return *this; } _Self - operator++(int) + operator++(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _Rb_tree_increment(_M_node); @@ -280,14 +280,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } _Self& - operator--() + operator--() _GLIBCXX_NOEXCEPT { _M_node = _Rb_tree_decrement(_M_node); return *this; } _Self - operator--(int) + operator--(int) _GLIBCXX_NOEXCEPT { _Self __tmp = *this; _M_node = _Rb_tree_decrement(_M_node); @@ -295,11 +295,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } bool - operator==(const _Self& __x) const + operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node == __x._M_node; } bool - operator!=(const _Self& __x) const + operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT { return _M_node != __x._M_node; } _Base_ptr _M_node; @@ -308,13 +308,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Val> inline bool operator==(const _Rb_tree_iterator<_Val>& __x, - const _Rb_tree_const_iterator<_Val>& __y) + const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT { return __x._M_node == __y._M_node; } template<typename _Val> inline bool operator!=(const _Rb_tree_iterator<_Val>& __x, - const _Rb_tree_const_iterator<_Val>& __y) + const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT { return __x._M_node != __y._M_node; } void @@ -370,7 +370,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return _M_impl._Node_allocator::allocate(1); } void - _M_put_node(_Link_type __p) + _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT { _M_impl._Node_allocator::deallocate(__p, 1); } #if __cplusplus < 201103L @@ -416,7 +416,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } void - _M_destroy_node(_Link_type __p) + _M_destroy_node(_Link_type __p) noexcept { _M_get_Node_allocator().destroy(__p); _M_put_node(__p); @@ -474,46 +474,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION protected: _Base_ptr& - _M_root() + _M_root() _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_parent; } _Const_Base_ptr - _M_root() const + _M_root() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_parent; } _Base_ptr& - _M_leftmost() + _M_leftmost() _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_left; } _Const_Base_ptr - _M_leftmost() const + _M_leftmost() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_left; } _Base_ptr& - _M_rightmost() + _M_rightmost() _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_right; } _Const_Base_ptr - _M_rightmost() const + _M_rightmost() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_header._M_right; } _Link_type - _M_begin() + _M_begin() _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } _Const_Link_type - _M_begin() const + _M_begin() const _GLIBCXX_NOEXCEPT { return static_cast<_Const_Link_type> (this->_M_impl._M_header._M_parent); } _Link_type - _M_end() + _M_end() _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(&this->_M_impl._M_header); } _Const_Link_type - _M_end() const + _M_end() const _GLIBCXX_NOEXCEPT { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } static const_reference @@ -525,19 +525,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return _KeyOfValue()(_S_value(__x)); } static _Link_type - _S_left(_Base_ptr __x) + _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(__x->_M_left); } static _Const_Link_type - _S_left(_Const_Base_ptr __x) + _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { return static_cast<_Const_Link_type>(__x->_M_left); } static _Link_type - _S_right(_Base_ptr __x) + _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(__x->_M_right); } static _Const_Link_type - _S_right(_Const_Base_ptr __x) + _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { return static_cast<_Const_Link_type>(__x->_M_right); } static const_reference @@ -549,19 +549,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return _KeyOfValue()(_S_value(__x)); } static _Base_ptr - _S_minimum(_Base_ptr __x) + _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT { return _Rb_tree_node_base::_S_minimum(__x); } static _Const_Base_ptr - _S_minimum(_Const_Base_ptr __x) + _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { return _Rb_tree_node_base::_S_minimum(__x); } static _Base_ptr - _S_maximum(_Base_ptr __x) + _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT { return _Rb_tree_node_base::_S_maximum(__x); } static _Const_Base_ptr - _S_maximum(_Const_Base_ptr __x) + _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT { return _Rb_tree_node_base::_S_maximum(__x); } public: diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index 726693918a3..03850b5e28f 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -87,18 +87,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } - _Vector_impl(_Tp_alloc_type const& __a) + _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } #if __cplusplus >= 201103L - _Vector_impl(_Tp_alloc_type&& __a) + _Vector_impl(_Tp_alloc_type&& __a) noexcept : _Tp_alloc_type(std::move(__a)), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } #endif - void _M_swap_data(_Vector_impl& __x) + void _M_swap_data(_Vector_impl& __x) _GLIBCXX_NOEXCEPT { std::swap(_M_start, __x._M_start); std::swap(_M_finish, __x._M_finish); @@ -124,7 +124,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Vector_base() : _M_impl() { } - _Vector_base(const allocator_type& __a) + _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT : _M_impl(__a) { } _Vector_base(size_t __n) @@ -136,10 +136,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_create_storage(__n); } #if __cplusplus >= 201103L - _Vector_base(_Tp_alloc_type&& __a) + _Vector_base(_Tp_alloc_type&& __a) noexcept : _M_impl(std::move(__a)) { } - _Vector_base(_Vector_base&& __x) + _Vector_base(_Vector_base&& __x) noexcept : _M_impl(std::move(__x._M_get_Tp_allocator())) { this->_M_impl._M_swap_data(__x._M_impl); } @@ -156,7 +156,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif - ~_Vector_base() + ~_Vector_base() _GLIBCXX_NOEXCEPT { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); } @@ -243,17 +243,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // [23.2.4.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) /** - * @brief Default constructor creates no elements. - */ - vector() - : _Base() { } - - /** * @brief Creates a %vector with no elements. * @param __a An allocator object. */ explicit - vector(const allocator_type& __a) + vector(const allocator_type& __a = allocator_type()) _GLIBCXX_NOEXCEPT : _Base(__a) { } #if __cplusplus >= 201103L @@ -767,7 +761,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * see at().) */ reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { return *(this->_M_impl._M_start + __n); } /** @@ -782,7 +776,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * see at().) */ const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { return *(this->_M_impl._M_start + __n); } protected: @@ -836,7 +830,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %vector. */ reference - front() + front() _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -844,7 +838,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %vector. */ const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return *begin(); } /** @@ -852,7 +846,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * element of the %vector. */ reference - back() + back() _GLIBCXX_NOEXCEPT { return *(end() - 1); } /** @@ -860,7 +854,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * last element of the %vector. */ const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { return *(end() - 1); } // _GLIBCXX_RESOLVE_LIB_DEFECTS @@ -934,7 +928,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * called. */ void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { --this->_M_impl._M_finish; _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); @@ -1415,7 +1409,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, // _M_assign_aux. void - _M_erase_at_end(pointer __pos) + _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT { std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); this->_M_impl._M_finish = __pos; diff --git a/libstdc++-v3/include/debug/array b/libstdc++-v3/include/debug/array index bce10cf3f12..d3eea853856 100644 --- a/libstdc++-v3/include/debug/array +++ b/libstdc++-v3/include/debug/array @@ -147,7 +147,7 @@ namespace __debug // Element access. reference - operator[](size_type __n) + operator[](size_type __n) noexcept { __glibcxx_check_subscript(__n); return _AT_Type::_S_ref(_M_elems, __n); @@ -180,14 +180,14 @@ namespace __debug } reference - front() + front() noexcept { __glibcxx_check_nonempty(); return *begin(); } constexpr const_reference - front() const + front() const noexcept { return _Nm ? _AT_Type::_S_ref(_M_elems, 0) : (_GLIBCXX_THROW_OR_ABORT(_Array_check_nonempty<_Nm>()), @@ -195,14 +195,14 @@ namespace __debug } reference - back() + back() noexcept { __glibcxx_check_nonempty(); return _Nm ? *(end() - 1) : *end(); } constexpr const_reference - back() const + back() const noexcept { return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1) : (_GLIBCXX_THROW_OR_ABORT(_Array_check_nonempty<_Nm>()), diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque index e5e902dfc7b..3984f11ac6b 100644 --- a/libstdc++-v3/include/debug/deque +++ b/libstdc++-v3/include/debug/deque @@ -128,7 +128,7 @@ namespace __debug #if __cplusplus >= 201103L deque& - operator=(deque&& __x) + operator=(deque&& __x) noexcept { // NB: DR 1204. // NB: DR 675. @@ -287,7 +287,7 @@ namespace __debug #if __cplusplus >= 201103L void - shrink_to_fit() + shrink_to_fit() noexcept { if (_Base::_M_shrink_to_fit()) this->_M_invalidate_all(); @@ -298,14 +298,14 @@ namespace __debug // element access: reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { __glibcxx_check_subscript(__n); return _M_base()[__n]; } const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { __glibcxx_check_subscript(__n); return _M_base()[__n]; @@ -314,28 +314,28 @@ namespace __debug using _Base::at; reference - front() + front() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); @@ -468,7 +468,7 @@ namespace __debug #endif void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); this->_M_invalidate_if(_Equal(_Base::begin())); @@ -476,7 +476,7 @@ namespace __debug } void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); this->_M_invalidate_if(_Equal(--_Base::end())); @@ -556,7 +556,7 @@ namespace __debug } void - swap(deque& __x) + swap(deque& __x) _GLIBCXX_NOEXCEPT { _Base::swap(__x); this->_M_swap(__x); diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index fd00b0148a9..89c26e425ae 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -70,7 +70,7 @@ namespace __debug // 23.2.2.1 construct/copy/destroy: explicit - list(const _Allocator& __a = _Allocator()) + list(const _Allocator& __a = _Allocator()) _GLIBCXX_NOEXCEPT : _Base(__a) { } #if __cplusplus >= 201103L @@ -320,28 +320,28 @@ namespace __debug // element access: reference - front() + front() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); @@ -355,7 +355,7 @@ namespace __debug #endif void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); this->_M_invalidate_if(_Equal(_Base::begin())); @@ -369,7 +369,7 @@ namespace __debug #endif void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); this->_M_invalidate_if(_Equal(--_Base::end())); @@ -455,7 +455,7 @@ namespace __debug private: _Base_iterator #if __cplusplus >= 201103L - _M_erase(_Base_const_iterator __position) + _M_erase(_Base_const_iterator __position) noexcept #else _M_erase(_Base_iterator __position) #endif @@ -467,7 +467,7 @@ namespace __debug public: iterator #if __cplusplus >= 201103L - erase(const_iterator __position) + erase(const_iterator __position) noexcept #else erase(iterator __position) #endif @@ -478,7 +478,7 @@ namespace __debug iterator #if __cplusplus >= 201103L - erase(const_iterator __first, const_iterator __last) + erase(const_iterator __first, const_iterator __last) noexcept #else erase(iterator __first, iterator __last) #endif @@ -515,7 +515,7 @@ namespace __debug // 23.2.2.4 list operations: void #if __cplusplus >= 201103L - splice(const_iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) noexcept #else splice(iterator __position, list& __x) #endif @@ -529,13 +529,13 @@ namespace __debug #if __cplusplus >= 201103L void - splice(const_iterator __position, list& __x) + splice(const_iterator __position, list& __x) noexcept { splice(__position, std::move(__x)); } #endif void #if __cplusplus >= 201103L - splice(const_iterator __position, list&& __x, const_iterator __i) + splice(const_iterator __position, list&& __x, const_iterator __i) noexcept #else splice(iterator __position, list& __x, iterator __i) #endif @@ -561,14 +561,14 @@ namespace __debug #if __cplusplus >= 201103L void - splice(const_iterator __position, list& __x, const_iterator __i) + splice(const_iterator __position, list& __x, const_iterator __i) noexcept { splice(__position, std::move(__x), __i); } #endif void #if __cplusplus >= 201103L splice(const_iterator __position, list&& __x, const_iterator __first, - const_iterator __last) + const_iterator __last) noexcept #else splice(iterator __position, list& __x, iterator __first, iterator __last) @@ -608,7 +608,7 @@ namespace __debug #if __cplusplus >= 201103L void splice(const_iterator __position, list& __x, - const_iterator __first, const_iterator __last) + const_iterator __first, const_iterator __last) noexcept { splice(__position, std::move(__x), __first, __last); } #endif diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string index 9e856c1ee8c..925575e662a 100644 --- a/libstdc++-v3/include/debug/string +++ b/libstdc++-v3/include/debug/string @@ -70,6 +70,7 @@ namespace __gnu_debug // 21.3.1 construct/copy/destroy: explicit basic_string(const _Allocator& __a = _Allocator()) + _GLIBCXX_NOEXCEPT : _Base(__a) { } @@ -238,7 +239,7 @@ namespace __gnu_debug #if __cplusplus >= 201103L void - shrink_to_fit() + shrink_to_fit() noexcept { if (capacity() > size()) { @@ -267,7 +268,7 @@ namespace __gnu_debug // 21.3.4 element access: const_reference - operator[](size_type __pos) const + operator[](size_type __pos) const _GLIBCXX_NOEXCEPT { _GLIBCXX_DEBUG_VERIFY(__pos <= this->size(), _M_message(__gnu_debug::__msg_subscript_oob) @@ -278,7 +279,7 @@ namespace __gnu_debug } reference - operator[](size_type __pos) + operator[](size_type __pos) _GLIBCXX_NOEXCEPT { #ifdef _GLIBCXX_DEBUG_PEDANTIC __glibcxx_check_subscript(__pos); @@ -582,7 +583,7 @@ namespace __gnu_debug #if __cplusplus >= 201103L void - pop_back() + pop_back() noexcept { __glibcxx_check_nonempty(); _Base::pop_back(); diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index 7b28177c2a0..e5b80649b9a 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -76,7 +76,7 @@ namespace __debug // 23.2.4.1 construct/copy/destroy: explicit - vector(const _Allocator& __a = _Allocator()) + vector(const _Allocator& __a = _Allocator()) _GLIBCXX_NOEXCEPT : _Base(__a), _M_guaranteed_capacity(0) { } #if __cplusplus >= 201103L @@ -341,14 +341,14 @@ namespace __debug // element access: reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { __glibcxx_check_subscript(__n); return _M_base()[__n]; } const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { __glibcxx_check_subscript(__n); return _M_base()[__n]; @@ -357,28 +357,28 @@ namespace __debug using _Base::at; reference - front() + front() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); return _Base::back(); @@ -419,7 +419,7 @@ namespace __debug #endif void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { __glibcxx_check_nonempty(); this->_M_invalidate_if(_Equal(--_Base::end())); @@ -630,18 +630,18 @@ namespace __debug size_type _M_guaranteed_capacity; bool - _M_requires_reallocation(size_type __elements) + _M_requires_reallocation(size_type __elements) _GLIBCXX_NOEXCEPT { return __elements > this->capacity(); } void - _M_update_guaranteed_capacity() + _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT { if (this->size() > _M_guaranteed_capacity) _M_guaranteed_capacity = this->size(); } void - _M_invalidate_after_nth(difference_type __n) + _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT { typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; this->_M_invalidate_if(_After_nth(__n, _Base::begin())); diff --git a/libstdc++-v3/include/ext/sso_string_base.h b/libstdc++-v3/include/ext/sso_string_base.h index 9e5b50e6e24..6cb4302b688 100644 --- a/libstdc++-v3/include/ext/sso_string_base.h +++ b/libstdc++-v3/include/ext/sso_string_base.h @@ -361,9 +361,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_capacity(__rcs._M_allocated_capacity); } - _M_length(__rcs._M_length()); - __rcs._M_length(0); + _M_set_length(__rcs._M_length()); __rcs._M_data(__rcs._M_local_data); + __rcs._M_set_length(0); } #endif diff --git a/libstdc++-v3/include/ext/vstring.h b/libstdc++-v3/include/ext/vstring.h index 85322130cf9..bd93c803c23 100644 --- a/libstdc++-v3/include/ext/vstring.h +++ b/libstdc++-v3/include/ext/vstring.h @@ -98,7 +98,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // NB: _M_limit doesn't check for a bad __pos value. size_type - _M_limit(size_type __pos, size_type __off) const + _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT { const bool __testoff = __off < this->size() - __pos; return __testoff ? __off : this->size() - __pos; @@ -106,7 +106,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // True if _Rep and source do not overlap. bool - _M_disjunct(const _CharT* __s) const + _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT { return (std::less<const _CharT*>()(__s, this->_M_data()) || std::less<const _CharT*>()(this->_M_data() @@ -116,11 +116,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // For the internal use we have functions similar to `begin'/`end' // but they do not call _M_leak. iterator - _M_ibegin() const + _M_ibegin() const _GLIBCXX_NOEXCEPT { return iterator(this->_M_data()); } iterator - _M_iend() const + _M_iend() const _GLIBCXX_NOEXCEPT { return iterator(this->_M_data() + this->_M_length()); } public: @@ -129,16 +129,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // arguments, per 17.4.4.4 para. 2 item 2. /** - * @brief Default constructor creates an empty string. - */ - __versa_string() - : __vstring_base() { } - - /** * @brief Construct an empty string using allocator @a a. */ explicit - __versa_string(const _Alloc& __a) + __versa_string(const _Alloc& __a = _Alloc()) _GLIBCXX_NOEXCEPT : __vstring_base(__a) { } // NB: per LWG issue 42, semantics different from IS: @@ -269,7 +263,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * copying). @a __str is a valid, but unspecified string. */ __versa_string& - operator=(__versa_string&& __str) + operator=(__versa_string&& __str) noexcept { // NB: DR 1204. this->swap(__str); @@ -470,7 +464,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus >= 201103L /// A non-binding request to reduce capacity() to size(). void - shrink_to_fit() + shrink_to_fit() noexcept { if (capacity() > size()) { @@ -538,7 +532,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * see at().) */ const_reference - operator[] (size_type __pos) const + operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT { _GLIBCXX_DEBUG_ASSERT(__pos <= this->size()); return this->_M_data()[__pos]; @@ -555,7 +549,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * see at().) Unshares the string. */ reference - operator[](size_type __pos) + operator[](size_type __pos) _GLIBCXX_NOEXCEPT { // Allow pos == size() both in C++98 mode, as v3 extension, // and in C++11 mode. @@ -611,7 +605,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * element of the %string. */ reference - front() + front() _GLIBCXX_NOEXCEPT { return operator[](0); } /** @@ -619,7 +613,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * element of the %string. */ const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return operator[](0); } /** @@ -627,7 +621,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * element of the %string. */ reference - back() + back() _GLIBCXX_NOEXCEPT { return operator[](this->size() - 1); } /** @@ -635,7 +629,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * last element of the %string. */ const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { return operator[](this->size() - 1); } #endif @@ -814,7 +808,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @a __str is a valid, but unspecified string. */ __versa_string& - assign(__versa_string&& __str) + assign(__versa_string&& __str) noexcept { this->swap(__str); return *this; @@ -1631,7 +1625,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * constant time. */ void - swap(__versa_string& __s) + swap(__versa_string& __s) _GLIBCXX_NOEXCEPT { this->_M_swap(__s); } // String operations: diff --git a/libstdc++-v3/include/profile/array b/libstdc++-v3/include/profile/array index bd6da6ca396..33bdc952096 100644 --- a/libstdc++-v3/include/profile/array +++ b/libstdc++-v3/include/profile/array @@ -127,7 +127,7 @@ namespace __profile // Element access. reference - operator[](size_type __n) + operator[](size_type __n) noexcept { return _AT_Type::_S_ref(_M_elems, __n); } constexpr const_reference @@ -153,19 +153,19 @@ namespace __profile } reference - front() + front() noexcept { return *begin(); } constexpr const_reference - front() const + front() const noexcept { return _AT_Type::_S_ref(_M_elems, 0); } reference - back() + back() noexcept { return _Nm ? *(end() - 1) : *end(); } constexpr const_reference - back() const + back() const noexcept { return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1) : _AT_Type::_S_ref(_M_elems, 0); diff --git a/libstdc++-v3/include/profile/deque b/libstdc++-v3/include/profile/deque index c46618e27e4..52d474d4c11 100644 --- a/libstdc++-v3/include/profile/deque +++ b/libstdc++-v3/include/profile/deque @@ -117,7 +117,7 @@ namespace __profile #if __cplusplus >= 201103L deque& - operator=(deque&& __x) + operator=(deque&& __x) noexcept { // NB: DR 1204. // NB: DR 675. @@ -245,13 +245,13 @@ namespace __profile // element access: reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { return _M_base()[__n]; } const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { return _M_base()[__n]; } @@ -259,25 +259,25 @@ namespace __profile using _Base::at; reference - front() + front() _GLIBCXX_NOEXCEPT { return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { return _Base::back(); } @@ -375,13 +375,13 @@ namespace __profile #endif void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { _Base::pop_front(); } void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { _Base::pop_back(); } @@ -409,7 +409,7 @@ namespace __profile } void - swap(deque& __x) + swap(deque& __x) _GLIBCXX_NOEXCEPT { _Base::swap(__x); } diff --git a/libstdc++-v3/include/profile/list b/libstdc++-v3/include/profile/list index ac09aa3db26..6168c61ed18 100644 --- a/libstdc++-v3/include/profile/list +++ b/libstdc++-v3/include/profile/list @@ -65,7 +65,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > // 23.2.2.1 construct/copy/destroy: explicit - list(const _Allocator& __a = _Allocator()) + list(const _Allocator& __a = _Allocator()) _GLIBCXX_NOEXCEPT : _Base(__a) { __profcxx_list_construct(this); // list2slist @@ -276,22 +276,22 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > // element access: reference - front() + front() _GLIBCXX_NOEXCEPT { return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { __profcxx_list_rewind(this); return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { __profcxx_list_rewind(this); return _Base::back(); @@ -311,7 +311,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #endif void - pop_front() + pop_front() _GLIBCXX_NOEXCEPT { __profcxx_list_operation(this); _Base::pop_front(); @@ -324,7 +324,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #endif void - pop_back() + pop_back() _GLIBCXX_NOEXCEPT { iterator __victim = end(); --__victim; @@ -411,7 +411,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > iterator #if __cplusplus >= 201103L - erase(const_iterator __position) + erase(const_iterator __position) noexcept #else erase(iterator __position) #endif @@ -419,7 +419,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > iterator #if __cplusplus >= 201103L - erase(const_iterator __position, const_iterator __last) + erase(const_iterator __position, const_iterator __last) noexcept #else erase(iterator __position, iterator __last) #endif @@ -440,7 +440,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > // 23.2.2.4 list operations: void #if __cplusplus >= 201103L - splice(const_iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) noexcept #else splice(iterator __position, list& __x) #endif @@ -448,7 +448,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #if __cplusplus >= 201103L void - splice(const_iterator __position, list& __x) + splice(const_iterator __position, list& __x) noexcept { this->splice(__position, std::move(__x)); } void @@ -458,7 +458,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > void #if __cplusplus >= 201103L - splice(const_iterator __position, list&& __x, const_iterator __i) + splice(const_iterator __position, list&& __x, const_iterator __i) noexcept #else splice(iterator __position, list& __x, iterator __i) #endif @@ -474,7 +474,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > void #if __cplusplus >= 201103L splice(const_iterator __position, list&& __x, const_iterator __first, - const_iterator __last) + const_iterator __last) noexcept #else splice(iterator __position, list& __x, iterator __first, iterator __last) @@ -490,7 +490,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #if __cplusplus >= 201103L void splice(const_iterator __position, list& __x, - const_iterator __first, const_iterator __last) + const_iterator __first, const_iterator __last) noexcept { this->splice(__position, std::move(__x), __first, __last); } #endif diff --git a/libstdc++-v3/include/profile/vector b/libstdc++-v3/include/profile/vector index 3ef04ff0a7c..8f79df7f07c 100644 --- a/libstdc++-v3/include/profile/vector +++ b/libstdc++-v3/include/profile/vector @@ -78,7 +78,7 @@ namespace __profile // 23.2.4.1 construct/copy/destroy: explicit - vector(const _Allocator& __a = _Allocator()) + vector(const _Allocator& __a = _Allocator()) _GLIBCXX_NOEXCEPT : _Base(__a) { __profcxx_vector_construct(this, this->capacity()); @@ -156,7 +156,7 @@ namespace __profile __profcxx_vector_construct2(this); } - vector(vector&& __x, const _Allocator& __a) noexcept + vector(vector&& __x, const _Allocator& __a) : _Base(std::move(__x), __a) { __profcxx_vector_construct(this, this->capacity()); @@ -292,13 +292,13 @@ namespace __profile // element access: reference - operator[](size_type __n) + operator[](size_type __n) _GLIBCXX_NOEXCEPT { __profcxx_vector_invalid_operator(this); return _M_base()[__n]; } const_reference - operator[](size_type __n) const + operator[](size_type __n) const _GLIBCXX_NOEXCEPT { __profcxx_vector_invalid_operator(this); return _M_base()[__n]; @@ -307,25 +307,25 @@ namespace __profile using _Base::at; reference - front() + front() _GLIBCXX_NOEXCEPT { return _Base::front(); } const_reference - front() const + front() const _GLIBCXX_NOEXCEPT { return _Base::front(); } reference - back() + back() _GLIBCXX_NOEXCEPT { return _Base::back(); } const_reference - back() const + back() const _GLIBCXX_NOEXCEPT { return _Base::back(); } diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array index 0d2a71c8cbc..86e8aee14ba 100644 --- a/libstdc++-v3/include/std/array +++ b/libstdc++-v3/include/std/array @@ -169,7 +169,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Element access. reference - operator[](size_type __n) + operator[](size_type __n) noexcept { return _AT_Type::_S_ref(_M_elems, __n); } constexpr const_reference @@ -195,19 +195,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } reference - front() + front() noexcept { return *begin(); } constexpr const_reference - front() const + front() const noexcept { return _AT_Type::_S_ref(_M_elems, 0); } reference - back() + back() noexcept { return _Nm ? *(end() - 1) : *end(); } constexpr const_reference - back() const + back() const noexcept { return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1) : _AT_Type::_S_ref(_M_elems, 0); |