Add the [[nodiscard]] attribute to several functions in <algorithm>.
These all have no side effects and are only called for their return
value (e.g. std::count) or produce a result that must not be discarded
for correctness (e.g. std::remove).
I was intending to add the attribute to a number of other functions like
std::copy_if, std::unique_copy, std::set_union, and std::set_difference.
I stopped when I noticed that MSVC doesn't use it on those functions,
which I suspect is because they're often used with an insert iterator
(e.g. std::back_insert_iterator). In that case it doesn't matter if
you discard the result, because you have the container to tell you how
many elements were copied to the output range.
libstdc++-v3/ChangeLog:
* include/bits/stl_algo.h (find_end, all_of, none_of, any_of)
(find_if_not, is_partitioned, partition_point, remove)
(remove_if, unique, lower_bound, upper_bound, equal_range)
(binary_search, includes, is_sorted, is_sorted_until, minmax)
(minmax_element, is_permutation, clamp, find_if, find_first_of)
(adjacent_find, count, count_if, search, search_n, min_element)
(max_element): Add nodiscard attribute.
* include/bits/stl_algobase.h (min, max, lower_bound, equal)
(lexicographical_compare, lexicographical_compare_three_way)
(mismatch): Likewise.
* include/bits/stl_heap.h (is_heap, is_heap_until): Likewise.
* testsuite/25_algorithms/equal/debug/1_neg.cc: Add dg-warning.
* testsuite/25_algorithms/equal/debug/2_neg.cc: Likewise.
* testsuite/25_algorithms/equal/debug/3_neg.cc: Likewise.
* testsuite/25_algorithms/find_first_of/concept_check_1.cc:
Likewise.
* testsuite/25_algorithms/is_permutation/2.cc: Likewise.
* testsuite/25_algorithms/lexicographical_compare/71545.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/33613.cc: Likewise.
* testsuite/25_algorithms/lower_bound/debug/irreflexive.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_pred_neg.cc:
Likewise.
* testsuite/25_algorithms/minmax/3.cc: Likewise.
* testsuite/25_algorithms/search/78346.cc: Likewise.
* testsuite/25_algorithms/search_n/58358.cc: Likewise.
* testsuite/25_algorithms/unique/1.cc: Likewise.
* testsuite/25_algorithms/unique/11480.cc: Likewise.
* testsuite/25_algorithms/upper_bound/33613.cc: Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_pred_neg.cc:
Likewise.
* testsuite/ext/concept_checks.cc: Likewise.
* testsuite/ext/is_heap/47709.cc: Likewise.
* testsuite/ext/is_sorted/cxx0x.cc: Likewise.
The change in r11-2981-g2f983fa69005b6 meant that
std::lexicographical_compare_three_way started to use memcmp for
unsigned integers on big endian targets, but for that to be valid we
need the two value types to have the same size and we need to use that
size to compute the length passed to memcmp.
I already defined a __is_memcmp_ordered_with trait that does the right
checks, std::lexicographical_compare_three_way just needs to use it.
libstdc++-v3/ChangeLog:
PR libstdc++/113960
* include/bits/stl_algobase.h (__is_byte_iter): Replace with ...
(__memcmp_ordered_with): New concept.
(lexicographical_compare_three_way): Use __memcmp_ordered_with
instead of __is_byte_iter. Use correct length for memcmp.
* testsuite/25_algorithms/lexicographical_compare_three_way/113960.cc:
New test.
In _GLIBCXX_DEBUG mode the std::__niter_base can remove 2 layers, the
__gnu_debug::_Safe_iterator<> and the __gnu_cxx::__normal_iterator<>.
When std::__niter_wrap is called to build a __gnu_debug::_Safe_iterator<>
from a __gnu_cxx::__normal_iterator<> we then have a consistency issue
as the difference between the 2 iterators will done on a __normal_iterator
on one side and a C pointer on the other. To avoid this problem call
std::__niter_base on both input iterators.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (std::__niter_wrap): Add a call to
std::__niter_base on res iterator.
std::__niter_base is used in _GLIBCXX_DEBUG mode to remove _Safe_iterator<>
wrapper on random access iterators. But doing so it should also preserve original
behavior to remove __normal_iterator wrapper.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (std::__niter_base): Redefine the overload
definitions for __gnu_debug::_Safe_iterator.
* include/debug/safe_iterator.tcc (std::__niter_base): Adapt declarations.
This makes constexpr std::vector (mostly) work in Debug Mode. All safe
iterator instrumentation and checking is disabled during constant
evaluation, because it requires mutex locks and calls to non-inline
functions defined in libstdc++.so. It should be OK to disable the safety
checks, because most UB should be detected during constant evaluation
anyway.
We could try to enable the full checking in constexpr, but it would mean
wrapping all the non-inline functions like _M_attach with an inline
_M_constexpr_attach that does the iterator housekeeping inline without
mutex locks when called for constant evaluation, and calls the
non-inline function at runtime. That could be done in future if we find
that we've lost safety or useful checking by disabling the safe
iterators.
There are a few test failures in C++20 mode, which I'm unable to
explain. The _Safe_iterator::operator++() member gives errors for using
non-constexpr functions during constant evaluation, even though those
functions are guarded by std::is_constant_evaluated() checks. The same
code works fine for C++23 and up.
libstdc++-v3/ChangeLog:
PR libstdc++/109536
* include/bits/c++config (__glibcxx_constexpr_assert): Remove
macro.
* include/bits/stl_algobase.h (__niter_base, __copy_move_a)
(__copy_move_backward_a, __fill_a, __fill_n_a, __equal_aux)
(__lexicographical_compare_aux): Add constexpr to overloads for
debug mode iterators.
* include/debug/helper_functions.h (__unsafe): Add constexpr.
* include/debug/macros.h (_GLIBCXX_DEBUG_VERIFY_COND_AT): Remove
macro, folding it into ...
(_GLIBCXX_DEBUG_VERIFY_AT_F): ... here. Do not use
__glibcxx_constexpr_assert.
* include/debug/safe_base.h (_Safe_iterator_base): Add constexpr
to some member functions. Omit attaching, detaching and checking
operations during constant evaluation.
* include/debug/safe_container.h (_Safe_container): Likewise.
* include/debug/safe_iterator.h (_Safe_iterator): Likewise.
* include/debug/safe_iterator.tcc (__niter_base, __copy_move_a)
(__copy_move_backward_a, __fill_a, __fill_n_a, __equal_aux)
(__lexicographical_compare_aux): Add constexpr.
* include/debug/vector (_Safe_vector, vector): Add constexpr.
Omit safe iterator operations during constant evaluation.
* testsuite/23_containers/vector/bool/capacity/constexpr.cc:
Remove dg-xfail-if for debug mode.
* testsuite/23_containers/vector/bool/cmp_c++20.cc: Likewise.
* testsuite/23_containers/vector/bool/cons/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/bool/element_access/1.cc:
Likewise.
* testsuite/23_containers/vector/bool/element_access/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/bool/modifiers/assign/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/bool/modifiers/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/bool/modifiers/swap/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/capacity/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/cmp_c++20.cc: Likewise.
* testsuite/23_containers/vector/cons/constexpr.cc: Likewise.
* testsuite/23_containers/vector/data_access/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/element_access/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/modifiers/assign/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/modifiers/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/modifiers/swap/constexpr.cc:
Likewise.
* testsuite/23_containers/vector/cons/destructible_debug_neg.cc:
Adjust dg-error line number.
This change moves the definitions of feature test macros (or strictly
speaking, the requests for <bits/version.h> to define them) so that only
standard headers define them. For example, <bits/shared_ptr.h> will no
longer define macros related to std::shared_ptr, only <memory> and
<version> will define them. This means that __cpp_lib_shared_ptr_arrays
will not be defined by <future> or by other headers that include
<bits/shared_ptr.h>. It will only be defined when <memory> has been
included. This will discourage users from relying on transitive
includes.
As a result, internal headers that need to query the macros should use
the internal macros like __glibcxx_shared_ptr_arrays instead of
__cpp_lib_shared_ptr_arrays, as those internal macros are defined by the
internal headers after icluding <bits/version.h>. There are some
exceptions to this rule, because __cpp_lib_is_constant_evaluated is
defined by bits/c++config.h and so is available everywhere, and
__cpp_lib_three_way_comparison is defined by <compare> which several
headers are explicitly specified to include, so its macro is guaranteed
to be usable too.
N.B. not many internal headers actually need an explicit include of
<bits/version.h>, because most of them include <type_traits> and so get
all the __glibcxx_foo internal macros from there.
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h: Do not define standard feature
test macro here.
* include/bits/align.h: Likewise. Test internal macros instead
of standard macros.
* include/bits/alloc_traits.h: Likewise.
* include/bits/allocator.h: Likewise.
* include/bits/atomic_base.h: Likewise.
* include/bits/atomic_timed_wait.h: Likewise.
* include/bits/atomic_wait.h: Likewise.
* include/bits/basic_string.h: Likewise.
* include/bits/basic_string.tcc: Likewise.
* include/bits/char_traits.h: Likewise.
* include/bits/chrono.h: Likewise.
* include/bits/cow_string.h: Likewise.
* include/bits/forward_list.h: Likewise.
* include/bits/hashtable.h: Likewise.
* include/bits/ios_base.h: Likewise.
* include/bits/memory_resource.h: Likewise.
* include/bits/move.h: Likewise.
* include/bits/move_only_function.h: Likewise.
* include/bits/node_handle.h: Likewise.
* include/bits/ptr_traits.h: Likewise.
* include/bits/range_access.h: Likewise.
* include/bits/ranges_algo.h: Likewise.
* include/bits/ranges_cmp.h: Likewise.
* include/bits/ranges_util.h: Likewise.
* include/bits/semaphore_base.h: Likewise.
* include/bits/shared_ptr.h: Likewise.
* include/bits/shared_ptr_atomic.h: Likewise.
* include/bits/shared_ptr_base.h: Likewise.
* include/bits/stl_algo.h: Likewise.
* include/bits/stl_algobase.h: Likewise.
* include/bits/stl_function.h: Likewise.
* include/bits/stl_iterator.h: Likewise.
* include/bits/stl_list.h: Likewise.
* include/bits/stl_map.h: Likewise.
* include/bits/stl_pair.h: Likewise.
* include/bits/stl_queue.h: Likewise.
* include/bits/stl_stack.h: Likewise.
* include/bits/stl_tree.h: Likewise.
* include/bits/stl_uninitialized.h: Likewise.
* include/bits/stl_vector.h: Likewise.
* include/bits/unique_ptr.h: Likewise.
* include/bits/unordered_map.h: Likewise.
* include/bits/uses_allocator_args.h: Likewise.
* include/bits/utility.h: Likewise.
* include/bits/erase_if.h: Add comment.
* include/std/algorithm: Define standard feature test macros
here.
* include/std/atomic: Likewise.
* include/std/array: Likewise.
* include/std/chrono: Likewise.
* include/std/condition_variable: Likewise.
* include/std/deque: Likewise.
* include/std/format: Likewise.
* include/std/functional: Likewise.
* include/std/forward_list: Likewise.
* include/std/ios: Likewise.
* include/std/iterator: Likewise.
* include/std/list: Likewise.
* include/std/map: Likewise.
* include/std/memory: Likewise.
* include/std/numeric: Likewise.
* include/std/queue: Likewise.
* include/std/ranges: Likewise.
* include/std/regex: Likewise.
* include/std/set: Likewise.
* include/std/stack: Likewise.
* include/std/stop_token: Likewise.
* include/std/string: Likewise.
* include/std/string_view:
* include/std/tuple: Likewise.
* include/std/unordered_map:
* include/std/unordered_set:
* include/std/utility: Likewise.
* include/std/vector: Likewise.
* include/std/scoped_allocator: Query internal macros instead of
standard macros.
Some constexpr functions were inadvertently relying on relaxed constexpr
rules from later standards.
libstdc++-v3/ChangeLog:
* include/bits/chrono.h (duration_cast): Do not use braces
around statements for C++11 constexpr rules.
* include/bits/stl_algobase.h (__lg): Rewrite as a single
statement for C++11 constexpr rules.
* include/experimental/bits/fs_path.h (path::string): Use
_GLIBCXX17_CONSTEXPR not _GLIBCXX_CONSTEXPR for 'if constexpr'.
* include/std/charconv (__to_chars_8): Initialize variable for
C++17 constexpr rules.
Move the std::search definition from stl_algo.h to stl_algobase.h and use
the later in <functional>.
For consistency also move std::__parallel::search and associated helpers from
<parallel/stl_algo.h> to <parallel/stl_algobase.h> so that std::__parallel::search
is accessible along with std::search.
libstdc++-v3/ChangeLog:
* include/bits/stl_algo.h
(std::__search, std::search(_FwdIt1, _FwdIt1, _FwdIt2, _FwdIt2, _BinPred)): Move...
* include/bits/stl_algobase.h: ...here.
* include/std/functional: Replace <stl_algo.h> include by <stl_algobase.h>.
* include/parallel/algo.h (std::__parallel::search<_FIt1, _FIt2, _BinaryPred>)
(std::__parallel::__search_switch<_FIt1, _FIt2, _BinaryPred, _ItTag1, _ItTag2>):
Move...
* include/parallel/algobase.h: ...here.
* include/experimental/functional: Remove <bits/stl_algo.h> and <parallel/algorithm>
includes. Include <bits/stl_algobase.h>.
This avoids overwriting tail padding when algorithms like std::copy are
used to write a single value through a pointer to a base subobject.
The pointer arithmetic on a Base* is valid for N==1, but the copy/move
operation needs to be done using assignment, not a memmove or memcpy of
sizeof(Base) bytes.
Instead of putting a check for N==1 in all of copy, copy_n, move etc.
this adds it to the __copy_move and __copy_move_backward partial
specializations used for trivially copyable types. When N==1 those
partial specializations dispatch to new static member functions of the
partial specializations for non-trivial types, so that a copy/move
assignment is done appropriately for the _IsMove constant.
libstdc++-v3/ChangeLog:
PR libstdc++/108846
* include/bits/stl_algobase.h (__copy_move<false, false, RA>)
Add __assign_one static member function.
(__copy_move<true, false, RA>): Likewise.
(__copy_move<IsMove, true, RA>): Do not use memmove for a single
value.
(__copy_move_backward<IsMove, true, RA>): Likewise.
* testsuite/25_algorithms/copy/108846.cc: New test.
* testsuite/25_algorithms/copy_backward/108846.cc: New test.
* testsuite/25_algorithms/copy_n/108846.cc: New test.
* testsuite/25_algorithms/move/108846.cc: New test.
* testsuite/25_algorithms/move_backward/108846.cc: New test.
Some standard algorithms fail to compile when size_t or ptrdiff_t is
narrower than int. The __lg helper function is ambiguous if ptrdiff_t is
short or __int20, so replace it with a function template that works for
those types as well as signed/unsigned int/long/long long. The helpers
for stable_sort perform arithmetic on size values and assume the types
won't change, which isn't true if the type promotes to int.
libstdc++-v3/ChangeLog:
PR libstdc++/108221
* include/bits/stl_algobase.h (__lg): Replace six overloads with
a single function template for all integer types.
* include/bits/stl_algo.h (__merge_adaptive_resize): Cast
arithmetic results back to _Distance.
This adds checks for _GLIBCXX_HOSTED to a number of headers which are
not currently installed for freestanding, but need to be for P1642R11
support. For example, <iterator> needs to be installed for C++23
freestanding mode, but without stream iterators and streambuf iterators.
Similarly, <memory> needs to be installed, but without std::allocator
and std::shared_ptr. This change disables the non-freestanding parts of
those headers.
libstdc++-v3/ChangeLog:
PR libstdc++/106953
* include/backward/auto_ptr.h [!_GLIBCXX_HOSTED]: Do not define
shared_ptr members.
* include/bits/alloc_traits.h [!_GLIBCXX_HOSTED]: Do not declare
std::allocator_traits<std::allocator<T>> specializations for
freestanding.
* include/bits/memoryfwd.h [!_GLIBCXX_HOSTED] (allocator): Do
not declare for freestanding.
* include/bits/stl_algo.h [!_GLIBCXX_HOSTED] (stable_partition):
Do not define for freestanding.
[!_GLIBCXX_HOSTED] (merge, stable_sort): Do not use temporary
buffers for freestanding.
* include/bits/stl_algobase.h [!_GLIBCXX_HOSTED]: Do not declare
streambuf iterators and overloaded algorithms using them.
* include/bits/stl_uninitialized.h [!_GLIBCXX_HOSTED]: Do not
define specialized overloads for std::allocator.
* include/bits/unique_ptr.h [!_GLIBCXX_HOSTED] (make_unique)
(make_unique_for_overwrite, operator<<): Do not define for
freestanding.
* include/c_global/cstdlib [!_GLIBCXX_HOSTED] (_Exit): Declare.
Use _GLIBCXX_NOTHROW instead of throw().
* include/debug/assertions.h [!_GLIBCXX_HOSTED]: Ignore
_GLIBCXX_DEBUG for freestanding.
* include/debug/debug.h [!_GLIBCXX_DEBUG]: Likewise.
* include/std/bit [!_GLIBCXX_HOSTED]: Do not use the custom
__int_traits if <ext/numeric_traits.h> is available.
* include/std/functional [!_GLIBCXX_HOSTED]: Do not include
headers that aren't valid for freestanding.
(boyer_moore_searcher, boyer_moore_horspool_searcher): Do not
define for freestanding.
* include/std/iterator [!_GLIBCXX_HOSTED]: Do not include
headers that aren't valid for freestanding.
* include/std/memory [!_GLIBCXX_HOSTED]: Likewise.
* include/std/ranges [!_GLIBCXX_HOSTED] (istream_view): Do not
define for freestanding.
(views::__detail::__is_basic_string_view) [!_GLIBCXX_HOSTED]:
Do not define partial specialization for freestanding.
This adds std::__is_constant_evaluated() as a C++11 wrapper for
__builtin_is_constant_evaluated, but just returning false if the
built-in isn't supported by the compiler. This allows us to use it
throughout the library without checking __has_builtin every time.
Some uses in std::vector and std::string can only be constexpr when the
std::is_constant_evaluated() function actually works, so we might as
well guard them with a relevant macro and call that function directly,
rather than the built-in or std::__is_constant_evaluated().
The remaining checks of the __cpp_lib_is_constant_evaluated macro could
now be replaced by checking __cplusplus >= 202002 instead, but there's
no practical difference. We still need some kind of preprocessor check
there anyway.
libstdc++-v3/ChangeLog:
* doc/doxygen/user.cfg.in (PREDEFINED): Change macro name.
* include/bits/allocator.h (allocate, deallocate): Use
std::__is_constant_evaluated() unconditionally, instead of
checking whether std::is_constant_evaluated() (or the built-in)
can be used.
* include/bits/basic_string.h: Check new macro. call
std::is_constant_evaluated() directly in C++20-only code that is
guarded by a suitable macro.
* include/bits/basic_string.tcc: Likewise.
* include/bits/c++config (__is_constant_evaluated): Define.
(_GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED): Replace with ...
(_GLIBCXX_HAVE_IS_CONSTANT_EVALUATED): New macro.
* include/bits/char_traits.h (char_traits): Replace conditional
calls to std::is_constant_evaluated with unconditional calls to
std::__is_constant_evaluated.
* include/bits/cow_string.h: Use new macro.
* include/bits/ranges_algobase.h (__copy_or_move): Replace
conditional calls to std::is_constant_evaluated with unconditional
calls to std::__is_constant_evaluated.
(__copy_or_move_backward, __fill_n_fn): Likewise.
* include/bits/ranges_cmp.h (ranges::less): Likewise.
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Likewise.
* include/bits/stl_bvector.h: Call std::is_constant_evaluated
directly in C++20-only code that is guarded by a suitable macro.
* include/bits/stl_construct.h (_Construct, _Destroy, _Destroy_n):
Replace is_constant_evaluated with __is_constant_evaluated.
* include/bits/stl_function.h (greater, less, greater_equal)
(less_equal): Replace __builtin_is_constant_evaluated and
__builtin_constant_p with __is_constant_evaluated.
* include/bits/stl_vector.h: Call std::is_constant_evaluated()
in C++20-only code.
* include/debug/helper_functions.h (__check_singular): Use
__is_constant_evaluated instead of built-in, or remove check
entirely.
* include/std/array (operator<=>): Use __is_constant_evaluated
unconditionally.
* include/std/bit (__bit_ceil): Likewise.
* include/std/type_traits (is_constant_evaluated): Define using
'if consteval' if possible.
* include/std/version: Use new macro.
* libsupc++/compare: Use __is_constant_evaluated instead of
__builtin_is_constant_evaluated.
* testsuite/23_containers/array/tuple_interface/get_neg.cc:
Adjust dg-error lines.
This implements P1004R2 ("Making std::vector constexpr") for C++20.
For now, debug mode vectors are not supported in constant expressions.
To make that work we might need to disable all attaching/detaching of
safe iterators. That can be fixed later.
Co-authored-by: Josh Marshall <joshua.r.marshall.1991@gmail.com>
libstdc++-v3/ChangeLog:
* include/bits/alloc_traits.h (_Destroy): Make constexpr for
C++20 mode.
* include/bits/allocator.h (__shrink_to_fit::_S_do_it):
Likewise.
* include/bits/stl_algobase.h (__fill_a1): Declare _Bit_iterator
overload constexpr for C++20.
* include/bits/stl_bvector.h (_Bit_type, _S_word_bit): Move out
of inline namespace.
(_Bit_reference, _Bit_iterator_base, _Bit_iterator)
(_Bit_const_iterator, _Bvector_impl_data, _Bvector_base)
(vector<bool, A>>): Add constexpr to every member function.
(_Bvector_base::_M_allocate): Initialize storage during constant
evaluation.
(vector<bool, A>::_M_initialize_value): Use __fill_bvector_n
instead of memset.
(__fill_bvector_n): New helper function to replace memset during
constant evaluation.
* include/bits/stl_uninitialized.h (__uninitialized_copy<false>):
Move logic to ...
(__do_uninit_copy): New function.
(__uninitialized_fill<false>): Move logic to ...
(__do_uninit_fill): New function.
(__uninitialized_fill_n<false>): Move logic to ...
(__do_uninit_fill_n): New function.
(__uninitialized_copy_a): Add constexpr. Use __do_uninit_copy.
(__uninitialized_move_a, __uninitialized_move_if_noexcept_a):
Add constexpr.
(__uninitialized_fill_a): Add constexpr. Use __do_uninit_fill.
(__uninitialized_fill_n_a): Add constexpr. Use
__do_uninit_fill_n.
(__uninitialized_default_n, __uninitialized_default_n_a)
(__relocate_a_1, __relocate_a): Add constexpr.
* include/bits/stl_vector.h (_Vector_impl_data, _Vector_impl)
(_Vector_base, vector): Add constexpr to every member function.
(_Vector_impl::_S_adjust): Disable ASan annotation during
constant evaluation.
(_Vector_base::_S_use_relocate): Disable bitwise-relocation
during constant evaluation.
(vector::_Temporary_value): Use a union for storage.
* include/bits/vector.tcc (vector, vector<bool>): Add constexpr
to every member function.
* include/std/vector (erase_if, erase): Add constexpr.
* testsuite/23_containers/headers/vector/synopsis.cc: Add
constexpr for C++20 mode.
* testsuite/23_containers/vector/bool/cmp_c++20.cc: Change to
compile-only test using constant expressions.
* testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust
namespace for _S_word_bit.
* testsuite/23_containers/vector/bool/modifiers/insert/31370.cc:
Likewise.
* testsuite/23_containers/vector/cmp_c++20.cc: Likewise.
* testsuite/23_containers/vector/cons/89164.cc: Adjust errors
for C++20 and move C++17 test to ...
* testsuite/23_containers/vector/cons/89164_c++17.cc: ... here.
* testsuite/23_containers/vector/bool/capacity/constexpr.cc: New test.
* testsuite/23_containers/vector/bool/cons/constexpr.cc: New test.
* testsuite/23_containers/vector/bool/element_access/constexpr.cc: New test.
* testsuite/23_containers/vector/bool/modifiers/assign/constexpr.cc: New test.
* testsuite/23_containers/vector/bool/modifiers/constexpr.cc: New test.
* testsuite/23_containers/vector/bool/modifiers/swap/constexpr.cc: New test.
* testsuite/23_containers/vector/capacity/constexpr.cc: New test.
* testsuite/23_containers/vector/cons/constexpr.cc: New test.
* testsuite/23_containers/vector/data_access/constexpr.cc: New test.
* testsuite/23_containers/vector/element_access/constexpr.cc: New test.
* testsuite/23_containers/vector/modifiers/assign/constexpr.cc: New test.
* testsuite/23_containers/vector/modifiers/constexpr.cc: New test.
* testsuite/23_containers/vector/modifiers/swap/constexpr.cc: New test.
This reduces the preprocessed size of <deque>, <string> and <vector> by
not including <bits/stl_algo.h> for std::remove and std::remove_if.
Also unwrap iterators using __niter_base, to avoid redundant debug mode
checks.
PR libstdc++/92546
* include/bits/erase_if.h (__erase_nodes_if): Use __niter_base to
unwrap debug iterators.
* include/bits/refwrap.h: Do not error if included in C++03.
* include/bits/stl_algo.h (__remove_if): Move to ...
* include/bits/stl_algobase.h (__remove_if): ... here.
* include/std/deque (erase, erase_if): Use __remove_if instead of
remove and remove_if.
* include/std/string (erase, erase_if): Likewise.
* include/std/vector (erase, erase_if): Likewise.
This change is inspired by the suggestion in
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1715r0.html
The new std::__conditional_t alias template is functionally equivalent
to std::conditional_t but should be more efficient to compile, due to
only ever instantiating two specializations (std::__conditional<true>
and std::__conditional<false>) rather than a new specialization for
every use of std::conditional.
The new alias template is also available in C++11, unlike the C++14
std::conditional_t alias.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/std/type_traits (__conditional): New class template
for internal uses of std::conditional.
(__conditional_t): New alias template to replace conditional_t.
(__and_, __or_, __result_of_memfun, __result_of_memobj): Use
__conditional_t instead of conditional::type.
* include/bits/atomic_base.h (__atomic_impl::_Diff): Likewise.
* include/bits/hashtable.h (_Hashtable): Likewise.
* include/bits/hashtable_policy.h (_Node_iterator, _Insert_base)
(_Local_iterator): Likewise. Replace typedefs with
using-declarations.
* include/bits/move.h (move_if_noexcept): Use __conditional_t.
* include/bits/parse_numbers.h (_Select_int_base): Likewise.
* include/bits/ptr_traits.h (__make_not_void): Likewise.
* include/bits/ranges_algobase.h (__copy_or_move_backward)
(__copy_or_move): Likewise.
* include/bits/ranges_base.h (borrowed_iterator_t): Likewise.
* include/bits/ranges_util.h (borrowed_subrange_t): Likewise.
* include/bits/regex_compiler.h (_BracketMatcher): Use
__conditional_t. Replace typedefs with using-declarations.
* include/bits/shared_ptr_base.h (__shared_count): Use
__conditional_t.
* include/bits/stl_algobase.h (__copy_move, __copy_move_backward):
Likewise.
* include/bits/stl_iterator.h (__detail::__clamp_iter_cat)
(reverse_iterator::iterator_concept)
(__make_move_if_noexcept_iterator)
(iterator_traits<common_iterator<_It, _Sent>>)
(iterator_traits<counted_iterator<_It>>): Likewise.
* include/bits/stl_pair.h (_PCC, pair::operator=): Likewise.
* include/bits/stl_tree.h (_Rb_tree::insert_return_type)
(_Rb_tree::_M_clone_node): Likewise.
* include/bits/unique_ptr.h (unique_ptr(unique_ptr<U,E>&&)):
Likewise.
* include/bits/uses_allocator.h (__uses_alloc): Likewise.
(__is_uses_allocator_predicate): Likewise.
* include/debug/functions.h (__foreign_iterator_aux2): Likewise.
* include/experimental/any (any::_Manager, __any_caster):
Likewise.
* include/experimental/executor (async_completion): Likewise.
* include/experimental/functional (__boyer_moore_base_t):
Likewise.
* include/std/any (any::_Manager): Likewise.
* include/std/functional (__boyer_moore_base_t): Likewise.
* include/std/ranges (borrowed_iterator_t)
(borrowed_subrange_t, __detail::__maybe_present_t)
(__detail::__maybe_const_t, split_view): Likewise.
* include/std/tuple (__empty_not_final, tuple::operator=):
Likewise.
* include/std/variant (__detail::__variant::__get_t): Likewise.
The _OutputIteratorConcept should be checked using the correct value
category. The std::move_backward and std::copy_backward algorithms
should use _OutputIteratorConcept instead of _ConvertibleConcept.
In order to use the correct value category, the concept should use a
function that returns _ValueT instead of using an lvalue data member.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/bits/boost_concept_check.h (_OutputIteratorConcept):
Use a function to preserve value category of the type.
* include/bits/stl_algobase.h (copy, move, fill_n): Use a
reference as the second argument for _OutputIteratorConcept.
(copy_backward, move_backward): Use _OutputIteratorConcept
instead of _ConvertibleConcept.
This reverts c1676651b6 and uses the
__extension__ keyword to prevent pedantic warnings instead of diagnostic
pragmas.
This also adds the __extension__ keyword in <limits> and <bits/random.h>
where there are some more warnings that I missed in the previous commit.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/bits/cpp_type_traits.h (__INT_N): Use __extension__
instead of diagnostic pragmas.
* include/bits/functional_hash.h: Likewise.
* include/bits/iterator_concepts.h (__is_signed_int128)
(__is_unsigned_int128): Likewise.
* include/bits/max_size_type.h (__max_size_type): Likewise.
(numeric_limits<__max_size_type>): Likewise.
* include/bits/std_abs.h (abs): Likewise.
* include/bits/stl_algobase.h (__size_to_integer): Likewise.
* include/bits/uniform_int_dist.h (uniform_int_distribution):
Likewise.
* include/ext/numeric_traits.h (_GLIBCXX_INT_N_TRAITS):
Likewise.
* include/std/type_traits (__is_integral_helper<INT_N>)
(__is_signed_integer, __is_unsigned_integer)
(__make_unsigned<INT_N>, __make_signed<INT_N>): Likewise.
* include/std/limits (__INT_N): Add __extension__ keyword.
* include/bits/random.h (_Select_uint_least_t)
(random_device): Likewise.
With -std=c++NN -pedantic -Wsystem-headers there are warnings about the
use of __int128, which can be suppressed using diagnostic pragmas.
Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
* include/bits/cpp_type_traits.h: Add diagnostic pragmas around
uses of non-standard integer types.
* include/bits/functional_hash.h: Likewise.
* include/bits/iterator_concepts.h: Likewise.
* include/bits/max_size_type.h: Likewise.
* include/bits/std_abs.h: Likewise.
* include/bits/stl_algobase.h: Likewise.
* include/bits/uniform_int_dist.h: Likewise.
* include/ext/numeric_traits.h: Likewise.
* include/std/type_traits: Likewise.
The message used for static assertions should be phrased so that it's
unambiguous whether the condition should be true or false. The message
should definitely not state the negative condition.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (__copy_move, __copy_move_backward):
Improve static_assert messages.
* testsuite/25_algorithms/copy/58982.cc: Adjust expected output.
* testsuite/25_algorithms/copy_n/58982.cc: Likewise.
The doxygen comments for these algos all incorrectly claim to use
(first - last) as the difference from the start of the output range to
the return value. As reported on the mailing list by Johannes Choo, it
should be (last - first).
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (copy, move, copy_backward)
(move_backward): Fix documentation for returned iterator.
The spaceship operator for std::array uses memcmp when the
__is_byte<value_type> trait is true, but memcmp isn't usable in
constexpr contexts. Also, memcmp should only be used for unsigned byte
types, because it gives the wrong answer for signed chars with negative
values.
We can simply check std::is_constant_evaluated() so that we don't use
memcmp during constant evaluation.
To fix the problem of using memcmp for inappropriate types, this patch
adds new __is_memcmp_ordered and __is_memcmp_ordered_with traits. These
say whether using memcmp will give the right answer for ordering
operations such as lexicographical_compare and three-way comparisons.
The new traits can be used in several places, and can also be used to
implement my suggestion in PR 93059 comment 37 to use memcmp for
unsigned integers larger than one byte on big endian targets.
libstdc++-v3/ChangeLog:
PR libstdc++/96851
* include/bits/cpp_type_traits.h (__is_memcmp_ordered):
New trait that says if memcmp can be used for ordering.
(__is_memcmp_ordered_with): Likewise, for two types.
* include/bits/deque.tcc (__lex_cmp_dit): Use new traits
instead of __is_byte and __numeric_traits.
(__lexicographical_compare_aux1): Likewise.
* include/bits/ranges_algo.h (__lexicographical_compare_fn):
Likewise.
* include/bits/stl_algobase.h (__lexicographical_compare_aux1)
(__is_byte_iter): Likewise.
* include/std/array (operator<=>): Likewise. Only use memcmp
when std::is_constant_evaluated() is false.
* testsuite/23_containers/array/comparison_operators/96851.cc:
New test.
* testsuite/23_containers/array/tuple_interface/get_neg.cc:
Adjust dg-error line numbers.
Make the memcmp optimization work for std::deque iterators and safe
iterators.
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
libstdc++-v3/ChangeLog:
2020-06-08 François Dumont <fdumont@gcc.gnu.org>
Jonathan Wakely <jwakely@redhat.com>
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): Define overloads for deque
iterators.
* include/bits/stl_algobase.h (__lexicographical_compare::__3way):
New static member function.
(__lexicographical_compare<true>::__3way): Likewise.
(__lexicographical_compare<true>::__lc): Use __3way.
(__lexicographical_compare_aux): Rename to
__lexicographical_compare_aux1 and declare overloads for deque
iterators.
(__lexicographical_compare_aux): Define new forwarding function
that calls __lexicographical_compare_aux1 and declare new overloads
for safe iterators.
(lexicographical_compare): Do not use __niter_base on
parameters.
* include/debug/safe_iterator.tcc
(__lexicographical_compare_aux): Define overloads for safe
iterators.
* testsuite/25_algorithms/lexicographical_compare/1.cc: Add
checks with random access iterators.
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New test.
Some new algorithms need to use _GLIBCXX_STD_A to refer to the "normal"
version of the algorithm, to workaround the namespace dance done for
parallel mode.
PR libstdc++/94971 (partial)
* include/bits/ranges_algo.h (ranges::__sample_fn): Qualify
std::sample using macro to work in parallel mode.
(__sort_fn): Likewise for std::sort.
(ranges::__nth_element_fn): Likewise for std::nth_element.
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Likewise for std::__min_cmp.
* include/parallel/algobase.h (lexicographical_compare_three_way):
Add to namespace std::__parallel.
Extend the overload so that it is used even when _GLIBCXX_DEBUG mode
is activated.
* include/bits/stl_algobase.h (struct _Bit_iterator): New declaration.
(std::__fill_a1(_Bit_iterator, _Bit_iterator, const bool&)): Likewise.
* include/bits/stl_bvector.h (__fill_bvector): Move outside
_GLIBCXX_STD_C namespace.
(fill(_Bit_iterator, _Bit_iterator, const bool&)): Likewise and rename
into...
(__fill_a1): ...this.
* testsuite/25_algorithms/fill/bvector/1.cc: New.
The overload for byte types uses memset and isn't constexpr. This adds
the specifier and uses std::is_constant_evaluated() to provide a
compile-time alternative.
PR libstdc++/94933
* include/bits/stl_algobase.h (__fill_a1): Make overload for byte types
usable in constant expressions.
* testsuite/25_algorithms/fill_n/constexpr.cc: Test with bytes and
non-scalars.
Clang 9 supports C++20 via -std=c++2a but doesn't support Concepts, so
several of the new additions related to the Ranges library fail to
compile with -std=c++2a. The new definition of iterator_traits and the
definition of default_sentinel_t are guarded by __cpp_lib_concepts, so
check that in addition to __cplusplus > 201703L.
* include/bits/stl_algobase.h (__lexicographical_compare_aux): Check
__cpp_lib_concepts before using iter_reference_t.
* include/bits/stream_iterator.h (istream_iterator): Check
__cpp_lib_concepts before using default_sentinel_t.
* include/bits/streambuf_iterator.h (istreambuf_iterator): Likewise.
Several algorithms check the is_trivially_copyable trait to decide
whether to dispatch to memmove or memcmp as an optimization. Since
r271435 (CWG DR 2094) the trait is true for volatile-qualified scalars,
but we can't use memmove or memcmp when the type is volatile. We need to
also check for volatile types.
This is complicated by the fact that in C++20 (but not earlier standards)
iterator_traits<volatile T*>::value_type is T, so we can't just check
whether the value_type is volatile.
The solution in this patch is to introduce new traits __memcpyable and
__memcmpable which combine into a single trait the checks for pointers,
the value types being the same, and the type being trivially copyable
but not volatile-qualified.
PR libstdc++/94013
* include/bits/cpp_type_traits.h (__memcpyable, __memcmpable): New
traits to control when to use memmove and memcmp optimizations.
(__is_nonvolatile_trivially_copyable): New helper trait.
* include/bits/ranges_algo.h (__lexicographical_compare_fn): Do not
use memcmp optimization with volatile data.
* include/bits/ranges_algobase.h (__equal_fn): Use __memcmpable.
(__copy_or_move, __copy_or_move_backward): Use __memcpyable.
* include/bits/stl_algobase.h (__copy_move_a2): Use __memcpyable.
(__copy_move_backward_a2): Likewise.
(__equal_aux1): Use __memcmpable.
(__lexicographical_compare_aux): Do not use memcmp optimization with
volatile data.
* testsuite/25_algorithms/copy/94013.cc: New test.
* testsuite/25_algorithms/copy_backward/94013.cc: New test.
* testsuite/25_algorithms/equal/94013.cc: New test.
* testsuite/25_algorithms/fill/94013.cc: New test.
* testsuite/25_algorithms/lexicographical_compare/94013.cc: New test.
* testsuite/25_algorithms/move/94013.cc: New test.
* testsuite/25_algorithms/move_backward/94013.cc: New test.
As noted in LWG 3410 the specification in the C++20 draft performs more
iterator comparisons than necessary when the end of either range is
reached. Our implementation followed that specification. This removes
the redundant comparisons so that we do no unnecessary work as soon as
we find that we've reached the end of either range.
The odd-looking return statement is because it generates better code
than the original version that copied the global constants.
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Avoid redundant iterator comparisons (LWG 3410).
The new 25_algorithms/lexicographical_compare/93972.cc test fails on
targets where char is unsigned, revealing an existing regression with
the std::__memcmp helper that had gone unnoticed in
std::lexicographical_compare. When comparing char and unsigned char, the
memcmp optimisation is enabled, but the new std::__memcmp function fails
to compile for mismatched types.
PR libstdc++/93972
* include/bits/stl_algobase.h (__memcmp): Allow pointer types to
differ.
* testsuite/25_algorithms/lexicographical_compare/uchar.cc: New test.
Move std::is_permutation algorithm with associated helpers to stl_algobase.h
to remove stl_algo.h include from hashtable_policy.h and so reduce preprocess
size of unordered_map and unordered_set headers.
* include/bits/stl_algo.h
(__find_if, __count_if, __is_permutation, std::is_permutation): Move...
* include/bits/stl_algobase.h: ...here.
* include/bits/hashtable_policy.h: Remove <bits/stl_algo.h> include.
* include/bits/ranges_algo.h (__lexicographical_compare_fn): Declare
variables in smaller scope and avoid calling ranges::distance when we
know they are pointers. Remove statically-unreachable use of
__builtin_unreachable().
* include/bits/stl_algobase.h (__lexicographical_compare::__lc):
Define inline.
The mutating sequence algorithms std::copy, std::copy_backward,
std::move and std::move_backward conditionally use __builtin_memmove
for trivially copyable types. However, because memmove isn't usable in
constant expressions the use of __builtin_memmove is wrapped in a
__memmove function which replaces __builtin_memmove with a handwritten
loop when std::is_constant_evaluated() is true.
This means we have a manual loop for non-trivially copyable cases, and a
different manual loop for trivially copyable but constexpr cases. The
latter loop has incorrect semantics for the {copy,move}_backward cases
and so isn't used for them. Until earlier today the latter loop also had
incorrect semantics for the std::move cases, trying to move from const
rvalues.
The approach taken by this patch is to remove the __memmove function
entirely and use the original (and correct) manual loops for the
constexpr cases as well as the non-trivially copyable cases. This was
already done for move_backward and copy_backward, but was incorrectly
turning copy_backward into move_backward, by failing to use the _IsMove
constant to select the right specialization. This patch also fixes that.
* include/bits/ranges_algobase.h (__copy_or_move): Do not use memmove
during constant evaluation. Call __builtin_memmove directly instead of
__memmove.
(__copy_or_move_backward): Likewise.
* include/bits/stl_algobase.h (__memmove): Remove.
(__copy_move<M, true, random_access_iterator_tag>::__copy_m)
(__copy_move_backward<M, true, random_access_iterator_tag>::__copy_m):
Use __builtin_memmove directly instead of __memmove.
(__copy_move_a2): Do not use memmove during constant evaluation.
(__copy_move_backward_a2): Use _IsMove constant to select correct
__copy_move_backward specialization.
* testsuite/25_algorithms/copy_backward/constexpr.cc: Check for copies
begin turned into moves during constant evaluation.
The std::move and std::move_backward algorithms dispatch to the
std::__memmove helper when appropriate. That function uses a
pointer-to-const for the source values, preventing them from being
moved. The two callers of that function have the same problem.
Rather than altering __memmove and its callers to work with const or
non-const source pointers, this takes a more conservative approach of
casting away the const at the point where we want to do a move
assignment. This relies on the fact that we only use __memmove when the
type is trivially copyable, so we know the move assignment doesn't alter
the source anyway.
PR libstdc++/93872
* include/bits/stl_algobase.h (__memmove): Cast away const before
doing move assignment.
* testsuite/25_algorithms/move/93872.cc: New test.
* testsuite/25_algorithms/move_backward/93872.cc: New test.
The __iter_swap class template and explicit specialization are only
declared (and used) for C++03 so _GLIBCXX20_CONSTEXPR does nothing here.
* include/bits/stl_algobase.h (__iter_swap, __iter_swap<true>): Remove
redundant _GLIBCXX20_CONSTEXPR.
The contents of the <compare> header are not complete unless concepts
are supported, so the feature test macro should depend on the macro for
concepts.
As a result, the std::lexicographical_compare_three_way function will
not be defined unless concepts are supported, so there is no need to
check __cpp_lib_concepts before using concepts in those functions.
* include/bits/stl_algobase.h (__is_byte_iter, __min_cmp)
(lexicographical_compare_three_way): Do not depend on
__cpp_lib_concepts.
* include/std/version (__cpp_lib_three_way_comparison): Only define
when __cpp_lib_concepts is defined.
* libsupc++/compare (__cpp_lib_three_way_comparison): Likewise.
From-SVN: r279896
Clang now supports three-way comparisons. That causes both overloads of
std::lexicographical_compare_three_way to be defined, but the second one
uses std::compare_three_way which depends on concepts. Clang does not
yet support concepts, so the second overload should also depend on
__cpp_lib_concepts.
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Only define four-argument overload when __cpp_lib_concepts is defined.
From-SVN: r279861
The memmove optimizations for std::uninitialized_copy/fill/_n will
compile even if the type is not copy constructible, because std::copy
doesn't require copy construction to work. But the uninitialized
algorithms do require it.
This adds explicit static assertions to ensure we don't allow ill-formed
initializations.
PR libstdc++/89164
* include/bits/stl_algobase.h (__copy_move): Give descriptive names
to template parameters.
* include/bits/stl_uninitialized.h (uninitialized_copy)
(uninitialized_fill, uninitialized_fill_n): Add static assertions to
diagnose invalid uses.
* testsuite/20_util/specialized_algorithms/uninitialized_copy/1.cc:
Adjust expected error.
* testsuite/20_util/specialized_algorithms/uninitialized_copy/89164.cc:
New test.
* testsuite/20_util/specialized_algorithms/uninitialized_copy_n/
89164.cc: New test.
* testsuite/20_util/specialized_algorithms/uninitialized_fill/89164.cc:
New test.
* testsuite/20_util/specialized_algorithms/uninitialized_fill_n/
89164.cc: New test.
* testsuite/23_containers/vector/cons/89164.cc: New test.
* testsuite/23_containers/vector/cons/89164_c++17.cc: New test.
From-SVN: r275177
