Louis Dionne 0bbb936729 [libc++] Fix broken precondition of __bit_log2 (#155476) ...

In #135303, we started using `__bit_log2` instead of `__log2i` inside
`std::sort`. However, `__bit_log2` has a precondition that `__log2i`
didn't have, which is that the input is non-zero. While it technically
makes no sense to request the logarithm of 0, `__log2i` handled that
case and returned 0 without issues.

After switching to `__bit_log2`, passing 0 as an input results in an
unsigned integer overflow which can trigger
`-fsanitize=unsigned-integer-overflow`. While not technically UB in
itself, it's clearly not intended either.

To fix this, we add an internal assertion to `__bit_log2` which catches
the issue in our test suite, and we make sure not to violate
`__bit_log2`'s preconditions before we call it from `std::sort`.

(cherry picked from commit 2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080)

2025-09-09 10:33:32 +02:00

..

adjacent_find.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

all_of.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

any_of.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

binary_search.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

clamp.h

…

comp_ref_type.h

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

2025-01-08 11:12:59 -05:00

comp.h

Reapply "[libc++] Simplify the implementation of std::sort a bit (#104902)" (#114023)

2024-10-30 11:51:55 +01:00

copy_backward.h

[libc++] Fix copy_backward for vector<bool> with small storage types (#131560)

2025-03-19 11:58:02 -04:00

copy_if.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

copy_move_common.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

copy_n.h

…

copy.h

[libc++] Fix {std, ranges}::copy for vector<bool> with small storage types (#131545)

2025-03-19 11:55:51 -04:00

count_if.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

count.h

[libc++] Fix ambiguous call in {ranges, std}::count (#122529)

2025-03-19 11:36:29 -04:00

equal_range.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

equal.h

[libc++] Fix {std, ranges}::equal for vector<bool> with small storage types (#130394)

2025-03-19 11:51:21 -04:00

fill_n.h

[libc++] Fix UB in bitwise logic of {std, ranges}::{fill, fill_n} algorithms (#122410)

2025-02-05 11:39:49 -05:00

fill.h

…

find_end.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

find_first_of.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

find_if_not.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

find_if.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

find_segment_if.h

…

find.h

[libc++] Fix ambiguous call in {ranges, std}::find (#122641)

2025-03-13 14:15:03 -04:00

for_each_n_segment.h

[libc++] Optimize std::for_each_n for segmented iterators (#135468)

2025-05-21 12:10:50 -04:00

for_each_n.h

[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators (#132896)

2025-06-18 12:22:47 -04:00

for_each_segment.h

…

for_each.h

[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators (#132896)

2025-06-18 12:22:47 -04:00

generate_n.h

…

generate.h

…

half_positive.h

…

in_found_result.h

…

in_fun_result.h

…

in_in_out_result.h

…

in_in_result.h

…

in_out_out_result.h

…

in_out_result.h

…

includes.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

inplace_merge.h

[libc++] Implement part of P2562R1: constexpr std::inplace_merge (#129008)

2025-03-19 07:42:23 +08:00

is_heap_until.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

is_heap.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

is_partitioned.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

is_permutation.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

is_sorted_until.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

is_sorted.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

iter_swap.h

…

iterator_operations.h

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

2025-01-08 11:12:59 -05:00

lexicographical_compare_three_way.h

…

lexicographical_compare.h

[libc++] Refactor the configuration macros to being always defined (#112094)

2024-11-06 10:39:19 +01:00

lower_bound.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

make_heap.h

…

make_projected.h

[libc++] Define an internal API for std::invoke and friends (#116637)

2025-01-20 18:00:15 +01:00

max_element.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

max.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

merge.h

[libc++] Remove some unused includes (#120219)

2024-12-18 21:10:27 +01:00

min_element.h

[libc++] Refactor ranges::{min, max, min_element, max_element} to use std::__min_element (#132418)

2025-03-27 09:05:37 -04:00

min_max_result.h

…

min.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

minmax_element.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

minmax.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

mismatch.h

Revert "Reapply "[libc++] Explicitly convert to masks in SIMD code (#107983)"" (#122022)

2025-01-08 18:14:39 +01:00

move_backward.h

[libc++] Optimize ranges::move{,_backward} for vector<bool>::iterator (#121109)

2025-02-19 11:36:45 -05:00

move.h

[libc++] Optimize ranges::move{,_backward} for vector<bool>::iterator (#121109)

2025-02-19 11:36:45 -05:00

next_permutation.h

…

none_of.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

nth_element.h

…

out_value_result.h

[libc++] Implement ranges::iota (#68494)

2025-04-05 13:46:11 +02:00

partial_sort_copy.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

partial_sort.h

…

partition_copy.h

…

partition_point.h

…

partition.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

pop_heap.h

…

prev_permutation.h

…

pstl.h

[libc++] Switch experimental library macros to 0/1 macros (#124030)

2025-01-24 09:34:42 +01:00

push_heap.h

…

radix_sort.h

[libc++] Extend the scope of radix sorting inside std::stable_sort to floating-point types (#129452)

2025-04-16 17:34:11 +08:00

ranges_adjacent_find.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_all_of.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_any_of.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_binary_search.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_clamp.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_contains_subrange.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_contains.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_copy_backward.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_copy_if.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_copy_n.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

ranges_copy.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

ranges_count_if.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_count.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_ends_with.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

ranges_equal_range.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_equal.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_fill_n.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

ranges_fill.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_find_end.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_find_first_of.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_find_if_not.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_find_if.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_find_last.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

ranges_find.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_fold.h

[libc++][NFC] Rename fold.h to ranges_fold.h (#109696)

2024-09-30 08:30:16 -04:00

ranges_for_each_n.h

[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators (#132896)

2025-06-18 12:22:47 -04:00

ranges_for_each.h

[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators (#132896)

2025-06-18 12:22:47 -04:00

ranges_generate_n.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

ranges_generate.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

ranges_includes.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_inplace_merge.h

[libc++] Implement part of P2562R1: constexpr ranges::inplace_merge (#131947)

2025-03-20 01:59:32 +08:00

ranges_is_heap_until.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_is_heap.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_is_partitioned.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_is_permutation.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_is_sorted_until.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_is_sorted.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_iterator_concept.h

[libc++] Qualify calls to nullary functions like __throw_foo (#122465)

2025-02-21 07:59:46 -05:00

ranges_lexicographical_compare.h

[libc++] Optimize lexicographical_compare (#65279)

2024-08-04 10:02:43 +02:00

ranges_lower_bound.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_make_heap.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_max_element.h

[libc++] Refactor ranges::{min, max, min_element, max_element} to use std::__min_element (#132418)

2025-03-27 09:05:37 -04:00

ranges_max.h

[libc++] Refactor ranges::{min, max, min_element, max_element} to use std::__min_element (#132418)

2025-03-27 09:05:37 -04:00

ranges_merge.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_min_element.h

[libc++] Refactor ranges::{min, max, min_element, max_element} to use std::__min_element (#132418)

2025-03-27 09:05:37 -04:00

ranges_min.h

[libc++] Refactor ranges::{min, max, min_element, max_element} to use std::__min_element (#132418)

2025-03-27 09:05:37 -04:00

ranges_minmax_element.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_minmax.h

Reapply "[libc++] Simplify the implementation of std::sort a bit (#104902)" (#114023)

2024-10-30 11:51:55 +01:00

ranges_mismatch.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_move_backward.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_move.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_next_permutation.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_none_of.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_nth_element.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_partial_sort_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_partial_sort.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_partition_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_partition_point.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_partition.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

ranges_pop_heap.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_prev_permutation.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_push_heap.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_remove_copy_if.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_remove_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_remove_if.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_remove.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_replace_copy_if.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_replace_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_replace_if.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_replace.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_reverse_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_reverse.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_rotate_copy.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_rotate.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_sample.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_search_n.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_search.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_set_difference.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

ranges_set_intersection.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_set_symmetric_difference.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

ranges_set_union.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

ranges_shuffle.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_sort_heap.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_sort.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_stable_partition.h

[libc++] Implement part of P2562R1: constexpr ranges::stable_partition (#129839)

2025-03-06 09:23:55 +08:00

ranges_stable_sort.h

[libc++] Implement part of P2562R1: constexpr ranges::stable_sort (#128860)

2025-03-07 01:27:48 +08:00

ranges_starts_with.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_swap_ranges.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_transform.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_unique_copy.h

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

2025-01-08 11:12:59 -05:00

ranges_unique.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

ranges_upper_bound.h

[libc++] Remove dedicated namespaces for ranges functions (#76543)

2024-08-01 08:54:06 -04:00

remove_copy_if.h

…

remove_copy.h

…

remove_if.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

remove.h

[libc++][NFC] Use [[__nodiscard__]] unconditionally (#80454)

2024-09-12 21:18:43 +02:00

replace_copy_if.h

…

replace_copy.h

…

replace_if.h

…

replace.h

…

reverse_copy.h

…

reverse.h

…

rotate_copy.h

…

rotate.h

[libc++] Optimize ranges::rotate for vector<bool>::iterator (#121168)

2025-03-13 14:07:23 -04:00

sample.h

…

search_n.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

search.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

set_difference.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

set_intersection.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

set_symmetric_difference.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

set_union.h

[libc++] Remove _AlgPolicy from std::copy and algorithms using std::copy (#115887)

2024-11-12 23:03:52 +01:00

shift_left.h

…

shift_right.h

…

shuffle.h

Revert "[libc++] Introduce ABI sensitive areas to avoid requiring _LIBCPP_HIDE_FROM_ABI everywhere (#131156)" (#141756)

2025-05-28 12:04:51 -04:00

sift_down.h

…

simd_utils.h

[libc++] Ensure that we vectorize algorithms on all Clang-based compilers (#132090)

2025-03-24 13:22:40 -04:00

sort_heap.h

…

sort.h

[libc++] Fix broken precondition of __bit_log2 (#155476)

2025-09-09 10:33:32 +02:00

stable_partition.h

[libc++] Implement part of P2562R1: constexpr std::stable_partition (#128868)

2025-03-04 09:23:29 +08:00

stable_sort.h

[libc++] Extend the scope of radix sorting inside std::stable_sort to floating-point types (#129452)

2025-04-16 17:34:11 +08:00

swap_ranges.h

[libc++] Optimize ranges::swap_ranges for vector<bool>::iterator (#121150)

2025-03-04 17:15:36 -05:00

three_way_comp_ref_type.h

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

2025-01-08 11:12:59 -05:00

transform.h

…

uniform_random_bit_generator_adaptor.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00

unique_copy.h

…

unique.h

[libc++] Forward more algorithms to the classic algorithms (#114674)

2024-11-06 12:10:06 +01:00

unwrap_iter.h

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

2025-01-08 11:12:59 -05:00

unwrap_range.h

…

upper_bound.h

[libc++][modules] Fix missing and incorrect includes (#108850)

2024-09-16 15:06:20 -04:00