// Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_HPP_INCLUDED #define FLUX_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_HPP_INCLUDED #define FLUX_CORE_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_CONCEPTS_HPP_INCLUDED #define FLUX_CORE_CONCEPTS_HPP_INCLUDED // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_UTILS_HPP_INCLUDED #define FLUX_CORE_UTILS_HPP_INCLUDED // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_ASSERT_HPP_INCLUDED #define FLUX_CORE_ASSERT_HPP_INCLUDED // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_CONFIG_HPP_INCLUDED #define FLUX_CORE_CONFIG_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_MACROS_HPP_INCLUDED #define FLUX_CORE_MACROS_HPP_INCLUDED #include #define FLUX_FWD(x) static_cast(x) #define FLUX_DECLVAL(...) ((static_cast<__VA_ARGS__(*)()noexcept>(nullptr))()) #ifdef __GNUC__ #define FLUX_ALWAYS_INLINE [[gnu::always_inline]] #else #define FLUX_ALWAYS_INLINE #endif #define FLUX_NO_UNIQUE_ADDRESS [[no_unique_address]] #define FLUX_FOR(_flux_var_decl_, ...) \ if (auto&& _flux_seq_ = __VA_ARGS__; true) \ for (auto _flux_cur_ = ::flux::first(_flux_seq_); \ !::flux::is_last(_flux_seq_, _flux_cur_); \ ::flux::inc(_flux_seq_, _flux_cur_)) \ if (_flux_var_decl_ = ::flux::read_at(_flux_seq_, _flux_cur_); true) #define FLUX_ASSERT(cond) (::flux::assert_(cond, "assertion '" #cond "' failed")) #define FLUX_DEBUG_ASSERT(cond) (::flux::assert_(!::flux::config::enable_debug_asserts || (cond), "assertion '" #cond "' failed")); #ifdef FLUX_MODULE_INTERFACE #define FLUX_EXPORT export #else #define FLUX_EXPORT #endif #endif // FLUX_CORE_MACROS_HPP_INCLUDED #include #include #include #define FLUX_ERROR_POLICY_TERMINATE 1 #define FLUX_ERROR_POLICY_UNWIND 2 #define FLUX_OVERFLOW_POLICY_ERROR 10 #define FLUX_OVERFLOW_POLICY_WRAP 11 #define FLUX_OVERFLOW_POLICY_IGNORE 12 #define FLUX_DIVIDE_BY_ZERO_POLICY_ERROR 100 #define FLUX_DIVIDE_BY_ZERO_POLICY_IGNORE 101 // Default error policy is terminate #define FLUX_DEFAULT_ERROR_POLICY FLUX_ERROR_POLICY_TERMINATE // Default overflow policy is error in debug builds, wrap in release builds #ifdef NDEBUG # define FLUX_DEFAULT_OVERFLOW_POLICY FLUX_OVERFLOW_POLICY_WRAP #else # define FLUX_DEFAULT_OVERFLOW_POLICY FLUX_OVERFLOW_POLICY_ERROR #endif // NDEBUG // Default divide by zero policy is error in debug builds, ignore in release builds #ifdef NDEBUG # define FLUX_DEFAULT_DIVIDE_BY_ZERO_POLICY FLUX_DIVIDE_BY_ZERO_POLICY_IGNORE #else # define FLUX_DEFAULT_DIVIDE_BY_ZERO_POLICY FLUX_DIVIDE_BY_ZERO_POLICY_ERROR #endif // NDEBUG // Select which error policy to use #if defined(FLUX_TERMINATE_ON_ERROR) # define FLUX_ERROR_POLICY FLUX_ERROR_POLICY_TERMINATE #elif defined(FLUX_UNWIND_ON_ERROR) # define FLUX_ERROR_POLICY FLUX_ERROR_POLICY_UNWIND #else # define FLUX_ERROR_POLICY FLUX_DEFAULT_ERROR_POLICY #endif // FLUX_TERMINATE_ON_ERROR // Should we print an error message before terminating? #ifndef FLUX_PRINT_ERROR_ON_TERMINATE # define FLUX_PRINT_ERROR_ON_TERMINATE 1 #endif // FLUX_PRINT_ERROR_ON_TERMINATE // Should we test debug assertions? #ifndef FLUX_ENABLE_DEBUG_ASSERTS # ifdef NDEBUG # define FLUX_ENABLE_DEBUG_ASSERTS 0 # else # define FLUX_ENABLE_DEBUG_ASSERTS 1 # endif #endif // Select which overflow policy to use #if defined(FLUX_ERROR_ON_OVERFLOW) # define FLUX_OVERFLOW_POLICY FLUX_OVERFLOW_POLICY_ERROR #elif defined(FLUX_WRAP_ON_OVERFLOW) # define FLUX_OVERFLOW_POLICY FLUX_OVERFLOW_POLICY_WRAP #elif defined(FLUX_IGNORE_OVERFLOW) # define FLUX_OVERFLOW_POLICY FLUX_OVERFLOW_POLICY_IGNORE #else # define FLUX_OVERFLOW_POLICY FLUX_DEFAULT_OVERFLOW_POLICY #endif // FLUX_ERROR_ON_OVERFLOW // Select which overflow policy to use #if defined(FLUX_ERROR_ON_DIVIDE_BY_ZERO) # define FLUX_DIVIDE_BY_ZERO_POLICY FLUX_DIVIDE_BY_ZERO_POLICY_ERROR #elif defined(FLUX_IGNORE_DIVIDE_BY_ZERO) # define FLUX_DIVIDE_BY_ZERO_POLICY FLUX_DIVIDE_BY_ZERO_POLICY_IGNORE #else # define FLUX_DIVIDE_BY_ZERO_POLICY FLUX_DEFAULT_DIVIDE_BY_ZERO_POLICY #endif // FLUX_ERROR_ON_DIVIDE_BY_ZERO // Should we try to use static bounds checking? #if !defined(FLUX_DISABLE_STATIC_BOUNDS_CHECKING) # if defined(__has_cpp_attribute) && defined(__has_builtin) # if __has_builtin(__builtin_constant_p) && __has_cpp_attribute(gnu::error) # define FLUX_HAVE_GCC_STATIC_BOUNDS_CHECKING 1 # endif # endif #endif // FLUX_DISABLE_STATIC_BOUNDS_CHECKING // Default int_t is ptrdiff_t #define FLUX_DEFAULT_INT_TYPE std::ptrdiff_t // Select which int type to use #ifndef FLUX_INT_TYPE #define FLUX_INT_TYPE FLUX_DEFAULT_INT_TYPE #endif namespace flux { FLUX_EXPORT enum class error_policy { terminate = FLUX_ERROR_POLICY_TERMINATE, unwind = FLUX_ERROR_POLICY_UNWIND }; FLUX_EXPORT enum class overflow_policy { ignore = FLUX_OVERFLOW_POLICY_IGNORE, wrap = FLUX_OVERFLOW_POLICY_WRAP, error = FLUX_OVERFLOW_POLICY_ERROR }; enum class divide_by_zero_policy { ignore = FLUX_DIVIDE_BY_ZERO_POLICY_IGNORE, error = FLUX_DIVIDE_BY_ZERO_POLICY_ERROR }; namespace config { FLUX_EXPORT using int_type = FLUX_INT_TYPE; static_assert(std::signed_integral && (sizeof(int_type) >= sizeof(std::ptrdiff_t)), "Custom FLUX_INT_TYPE must be a signed integer type at least as large as ptrdiff_t"); FLUX_EXPORT inline constexpr error_policy on_error = static_cast(FLUX_ERROR_POLICY); FLUX_EXPORT inline constexpr overflow_policy on_overflow = static_cast(FLUX_OVERFLOW_POLICY); FLUX_EXPORT inline constexpr divide_by_zero_policy on_divide_by_zero = static_cast(FLUX_DIVIDE_BY_ZERO_POLICY); FLUX_EXPORT inline constexpr bool print_error_on_terminate = FLUX_PRINT_ERROR_ON_TERMINATE; FLUX_EXPORT inline constexpr bool enable_debug_asserts = FLUX_ENABLE_DEBUG_ASSERTS; } // namespace config } // namespace flux #endif #include #include #include #include #include namespace flux { FLUX_EXPORT struct unrecoverable_error : std::logic_error { explicit inline unrecoverable_error(char const* msg) : std::logic_error(msg) {} }; namespace detail { struct runtime_error_fn { [[noreturn]] void operator()(char const* msg, std::source_location loc = std::source_location::current()) const { if constexpr (config::on_error == error_policy::unwind) { char buf[1024]; std::snprintf(buf, 1024, "%s:%u: Fatal error: %s", loc.file_name(), loc.line(), msg); throw unrecoverable_error(buf); } else { if constexpr (config::print_error_on_terminate) { std::fprintf(stderr, "%s:%u: Fatal error: %s\n", loc.file_name(), loc.line(), msg); } std::terminate(); } } }; } FLUX_EXPORT inline constexpr auto runtime_error = detail::runtime_error_fn{}; #ifdef FLUX_HAVE_GCC_STATIC_BOUNDS_CHECKING [[gnu::error("out-of-bounds sequence access detected")]] void static_bounds_check_failed(); // not defined #endif namespace detail { struct assert_fn { inline constexpr void operator()(bool cond, char const* msg, std::source_location loc = std::source_location::current()) const { if (cond) { return; } else { runtime_error(msg, std::move(loc)); } } }; struct bounds_check_fn { inline constexpr void operator()(bool cond, std::source_location loc = std::source_location::current()) const { if (!std::is_constant_evaluated()) { assert_fn{}(cond, "out of bounds sequence access", std::move(loc)); } } }; struct indexed_bounds_check_fn { template inline constexpr void operator()(T idx, T limit, std::source_location loc = std::source_location::current()) const { if (!std::is_constant_evaluated()) { #ifdef FLUX_HAVE_GCC_STATIC_BOUNDS_CHECKING if (__builtin_constant_p(idx) && __builtin_constant_p(limit)) { if (idx < T{0} || idx >= limit) { static_bounds_check_failed(); } } #endif assert_fn{}(idx >= T{0}, "index cannot be negative", loc); assert_fn{}(idx < limit, "out-of-bounds sequence access", loc); } } }; } // namespace detail FLUX_EXPORT inline constexpr auto assert_ = detail::assert_fn{}; FLUX_EXPORT inline constexpr auto bounds_check = detail::bounds_check_fn{}; FLUX_EXPORT inline constexpr auto indexed_bounds_check = detail::indexed_bounds_check_fn{}; } // namespace flux #endif // FLUX_CORE_ASSERT_HPP_INCLUDED #include #include #include #include #include #include // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_NUMERIC_HPP_INCLUDED #define FLUX_CORE_NUMERIC_HPP_INCLUDED #include namespace flux::num { FLUX_EXPORT inline constexpr auto wrapping_add = [](T lhs, T rhs) -> T { using U = std::make_unsigned_t; return static_cast(static_cast(lhs) + static_cast(rhs)); }; FLUX_EXPORT inline constexpr auto wrapping_sub = [](T lhs, T rhs) -> T { using U = std::make_unsigned_t; return static_cast(static_cast(lhs) - static_cast(rhs)); }; FLUX_EXPORT inline constexpr auto wrapping_mul = [](T lhs, T rhs) -> T { using U = std::make_unsigned_t; return static_cast(static_cast(lhs) * static_cast(rhs)); }; namespace detail { #if defined(__has_builtin) # if __has_builtin(__builtin_add_overflow) && \ __has_builtin(__builtin_sub_overflow) && \ __has_builtin(__builtin_mul_overflow) # define FLUX_HAVE_BUILTIN_OVERFLOW_OPS 1 # endif #endif #ifdef FLUX_HAVE_BUILTIN_OVERFLOW_OPS inline constexpr bool use_builtin_overflow_ops = true; #else inline constexpr bool use_builtin_overflow_ops = false; #endif #undef FLUX_HAVE_BUILTIN_OVERFLOW_OPS } FLUX_EXPORT template struct overflow_result { T value; bool overflowed; }; FLUX_EXPORT inline constexpr auto overflowing_add = [](T lhs, T rhs) -> overflow_result { if constexpr (detail::use_builtin_overflow_ops) { bool overflowed = __builtin_add_overflow(lhs, rhs, &lhs); return {lhs, overflowed}; } else { T value = wrapping_add(lhs, rhs); bool overflowed = ((lhs < T{}) == (rhs < T{})) && ((lhs < T{}) != (value < T{})); return {value, overflowed}; } }; FLUX_EXPORT inline constexpr auto overflowing_sub = [](T lhs, T rhs) -> overflow_result { if constexpr (detail::use_builtin_overflow_ops) { bool overflowed = __builtin_sub_overflow(lhs, rhs, &lhs); return {lhs, overflowed}; } else { T value = wrapping_sub(lhs, rhs); bool overflowed = (lhs >= T{} && rhs < T{} && value < T{}) || (lhs < T{} && rhs > T{} && value > T{}); return {value, overflowed}; } }; FLUX_EXPORT inline constexpr auto overflowing_mul = [](T lhs, T rhs) -> overflow_result { if constexpr (detail::use_builtin_overflow_ops) { bool overflowed = __builtin_mul_overflow(lhs, rhs, &lhs); return {lhs, overflowed}; } else { T value = wrapping_mul(lhs, rhs); return {value, lhs != 0 && value/lhs != rhs}; } }; FLUX_EXPORT inline constexpr auto checked_add = [](T lhs, T rhs, std::source_location loc = std::source_location::current()) -> T { if (std::is_constant_evaluated()) { return lhs + rhs; } else { if constexpr (config::on_overflow == overflow_policy::ignore) { return lhs + rhs; } else if constexpr (config::on_overflow == overflow_policy::wrap) { return wrapping_add(lhs, rhs); } else { auto res = overflowing_add(lhs, rhs); if (res.overflowed) { runtime_error("signed overflow in addition", loc); } return res.value; } } }; FLUX_EXPORT inline constexpr auto checked_sub = [](T lhs, T rhs, std::source_location loc = std::source_location::current()) -> T { if (std::is_constant_evaluated()) { return lhs - rhs; } else { if constexpr (config::on_overflow == overflow_policy::ignore) { return lhs - rhs; } else if constexpr (config::on_overflow == overflow_policy::wrap) { return wrapping_sub(lhs, rhs); } else { auto res = overflowing_sub(lhs, rhs); if (res.overflowed) { runtime_error("signed overflow in subtraction", loc); } return res.value; } } }; FLUX_EXPORT inline constexpr auto checked_mul = [](T lhs, T rhs, std::source_location loc = std::source_location::current()) -> T { if (std::is_constant_evaluated()) { return lhs * rhs; } else { if constexpr (config::on_overflow == overflow_policy::ignore) { return lhs * rhs; } else if constexpr (config::on_overflow == overflow_policy::wrap) { return wrapping_mul(lhs, rhs); } else { auto res = overflowing_mul(lhs, rhs); if (res.overflowed) { runtime_error("signed overflow in multiplication", loc); } return res.value; } } }; FLUX_EXPORT inline constexpr auto checked_pow = [](T base, U exponent, std::source_location loc = std::source_location::current()) -> T { T res{1}; for(U i{0}; i < exponent; i++) { res = checked_mul(res, base, loc); } return res; }; inline constexpr auto checked_div = [](T lhs, T rhs, std::source_location loc = std::source_location::current()) -> T { if (std::is_constant_evaluated()) { return lhs / rhs; } else { if constexpr (config::on_divide_by_zero == divide_by_zero_policy::ignore) { return lhs / rhs; } else { if (rhs == 0) { runtime_error("divide by zero", loc); } return lhs / rhs; } } }; inline constexpr auto checked_mod = [](T lhs, T rhs, std::source_location loc = std::source_location::current()) -> T { if (std::is_constant_evaluated()) { return lhs % rhs; } else { if constexpr (config::on_divide_by_zero == divide_by_zero_policy::ignore) { return lhs % rhs; } else { if (rhs == 0) { runtime_error("divide by zero", loc); } return lhs % rhs; } } }; } // namespace flux::num #endif namespace flux { /* * Useful helpers */ FLUX_EXPORT template concept decays_to = std::same_as, To>; namespace detail { struct copy_fn { template [[nodiscard]] constexpr auto operator()(T&& arg) const noexcept(std::is_nothrow_convertible_v>) -> std::decay_t { return FLUX_FWD(arg); } }; } // namespace detail FLUX_EXPORT inline constexpr auto copy = detail::copy_fn{}; namespace detail { template struct checked_cast_fn { template [[nodiscard]] constexpr auto operator()(From from) const -> To { if constexpr (requires { To{from}; }) { return To{from}; // not a narrowing conversion } else { To to = static_cast(from); FLUX_DEBUG_ASSERT(static_cast(to) == from); if constexpr (std::is_signed_v != std::is_signed_v) { FLUX_DEBUG_ASSERT((to < To{}) == (from < From{})); } return to; } } }; } // namespace detail FLUX_EXPORT template inline constexpr auto checked_cast = detail::checked_cast_fn{}; namespace detail { template concept any_of = (std::same_as || ...); } // namespace detail } // namespace flux #endif #include #include #include #include #include #include #if defined(__cpp_lib_ranges_zip) && (__cpp_lib_ranges_zip >= 202110L) #define FLUX_HAVE_CPP23_TUPLE_COMMON_REF #endif namespace flux { /* * Cursor concepts */ FLUX_EXPORT template concept cursor = std::movable; FLUX_EXPORT template concept regular_cursor = cursor && std::regular; FLUX_EXPORT template concept ordered_cursor = regular_cursor && std::totally_ordered; /* * Sequence concepts and associated types */ FLUX_EXPORT template struct sequence_traits; namespace detail { template using traits_t = sequence_traits>; } // namespace detail FLUX_EXPORT template using cursor_t = decltype(detail::traits_t::first(FLUX_DECLVAL(Seq&))); FLUX_EXPORT template using element_t = decltype(detail::traits_t::read_at(FLUX_DECLVAL(Seq&), FLUX_DECLVAL(cursor_t const&))); namespace detail { template concept has_element_type = requires { typename element_t; }; template struct value_type { using type = std::remove_cvref_t>; }; template requires requires { typename traits_t::value_type; } struct value_type { using type = typename traits_t::value_type; }; template requires requires { traits_t::using_primary_template; } && requires { typename T::value_type; } struct value_type { using type = typename T::value_type; }; template struct rvalue_element_type { using type = std::conditional_t>, std::add_rvalue_reference_t>>, element_t>; }; template concept has_move_at = requires (Seq& seq, cursor_t const& cur) { { traits_t::move_at(seq, cur) }; }; template requires has_move_at struct rvalue_element_type { using type = decltype(traits_t::move_at(FLUX_DECLVAL(T&), FLUX_DECLVAL(cursor_t const&))); }; } // namespace detail FLUX_EXPORT template using value_t = typename detail::value_type::type; FLUX_EXPORT using distance_t = flux::config::int_type; FLUX_EXPORT using index_t = flux::config::int_type; FLUX_EXPORT template using rvalue_element_t = typename detail::rvalue_element_type::type; FLUX_EXPORT template using common_element_t = std::common_reference_t, value_t&>; FLUX_EXPORT template using const_element_t = std::common_reference_t const&&, element_t>; namespace detail { template concept boolean_testable = std::convertible_to && requires (B&& b) { { !FLUX_FWD(b) } -> std::convertible_to; }; template using with_ref = T&; template concept can_reference = requires { typename with_ref; }; template >> concept sequence_concept = requires (Seq& seq) { { Traits::first(seq) } -> cursor; } && requires (Seq& seq, cursor_t const& cur) { { Traits::is_last(seq, cur) } -> boolean_testable; { Traits::read_at(seq, cur) } -> can_reference; } && requires (Seq& seq, cursor_t& cur) { { Traits::inc(seq, cur) }; } && #ifdef FLUX_HAVE_CPP23_TUPLE_COMMON_REF std::common_reference_with&&, value_t&> && std::common_reference_with&&, value_t const&> && #endif std::common_reference_with&&, rvalue_element_t&&>; } // namespace detail FLUX_EXPORT template concept sequence = detail::sequence_concept; namespace detail { template inline constexpr bool disable_multipass = false; template requires requires { T::disable_multipass; } && decays_to inline constexpr bool disable_multipass = T::disable_multipass; } // namespace detail FLUX_EXPORT template concept multipass_sequence = sequence && regular_cursor> && !detail::disable_multipass>; namespace detail { template >> concept bidirectional_sequence_concept = multipass_sequence && requires (Seq& seq, cursor_t& cur) { { Traits::dec(seq, cur) }; }; } // namespace detail FLUX_EXPORT template concept bidirectional_sequence = detail::bidirectional_sequence_concept; namespace detail { template >> concept random_access_sequence_concept = bidirectional_sequence && ordered_cursor> && requires (Seq& seq, cursor_t& cur, distance_t offset) { { Traits::inc(seq, cur, offset) }; } && requires (Seq& seq, cursor_t const& cur) { { Traits::distance(seq, cur, cur) } -> std::convertible_to; }; } // namespace detail FLUX_EXPORT template concept random_access_sequence = detail::random_access_sequence_concept; namespace detail { template >> concept bounded_sequence_concept = sequence && requires (Seq& seq) { { Traits::last(seq) } -> std::same_as>; }; } // namespace detail FLUX_EXPORT template concept bounded_sequence = detail::bounded_sequence_concept; namespace detail { template >> concept contiguous_sequence_concept = random_access_sequence && bounded_sequence && std::is_lvalue_reference_v> && std::same_as, std::remove_cvref_t>> && requires (Seq& seq) { { Traits::data(seq) } -> std::same_as>>; }; } // namespace detail FLUX_EXPORT template concept contiguous_sequence = detail::contiguous_sequence_concept; namespace detail { template >> concept sized_sequence_concept = sequence && (requires (Seq& seq) { { Traits::size(seq) } -> std::convertible_to; } || ( random_access_sequence && bounded_sequence )); } // namespace detail FLUX_EXPORT template concept sized_sequence = detail::sized_sequence_concept; FLUX_EXPORT template concept writable_sequence_of = sequence && requires (element_t elem, T&& item) { { elem = FLUX_FWD(item) } -> std::same_as&>; }; namespace detail { template inline constexpr bool is_infinite_seq = false; template requires requires { T::is_infinite; } && decays_to inline constexpr bool is_infinite_seq = T::is_infinite; } FLUX_EXPORT template concept infinite_sequence = sequence && detail::is_infinite_seq>; FLUX_EXPORT template concept read_only_sequence = sequence && std::same_as, const_element_t>; FLUX_EXPORT template concept const_iterable_sequence = // Seq and Seq const must both be sequences sequence && sequence && // Seq and Seq const must have the same cursor and value types std::same_as, cursor_t> && std::same_as, value_t> && // Seq and Seq const must have the same const_element type #ifdef FLUX_HAVE_CPP23_TUPLE_COMMON_REF std::same_as, const_element_t> && #endif // Seq and Seq const must model the same extended sequence concepts (multipass_sequence == multipass_sequence) && (bidirectional_sequence == bidirectional_sequence) && (random_access_sequence == random_access_sequence) && (contiguous_sequence == contiguous_sequence) && (bounded_sequence == bounded_sequence) && (sized_sequence == sized_sequence) && (infinite_sequence == infinite_sequence) && // If Seq is read-only, Seq const must be read-only as well (!read_only_sequence || read_only_sequence); namespace detail { template > constexpr bool is_ilist = false; template constexpr bool is_ilist> = true; template concept rvalue_sequence = std::is_object_v && std::move_constructible && sequence; template concept trivially_copyable_sequence = std::copyable && std::is_trivially_copyable_v && sequence; } FLUX_EXPORT template concept adaptable_sequence = (detail::rvalue_sequence || (std::is_lvalue_reference_v && detail::trivially_copyable_sequence>)) && !detail::is_ilist; FLUX_EXPORT template struct inline_sequence_base; namespace detail { template requires (!std::same_as>) void derived_from_inline_sequence_base_test(T const&, inline_sequence_base const&); template concept derived_from_inline_sequence_base = requires(T t) { derived_from_inline_sequence_base_test(t, t); }; } // namespace detail /* * Default sequence_traits implementation */ namespace detail { template concept has_nested_sequence_traits = requires { typename T::flux_sequence_traits; } && std::is_class_v; } template requires detail::has_nested_sequence_traits struct sequence_traits : T::flux_sequence_traits {}; } // namespace flux #endif // FLUX_CORE_CONCEPTS_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_DEFAULT_IMPLS_HPP_INCLUDED #define FLUX_CORE_DEFAULT_IMPLS_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_SEQUENCE_ACCESS_HPP_INCLUDED #define FLUX_CORE_SEQUENCE_ACCESS_HPP_INCLUDED // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_OPTIONAL_HPP_INCLUDED #define FLUX_CORE_OPTIONAL_HPP_INCLUDED #include #include namespace flux { FLUX_EXPORT using nullopt_t = std::nullopt_t; FLUX_EXPORT inline constexpr nullopt_t const& nullopt = std::nullopt; namespace detail { template concept can_optional = (std::is_object_v || std::is_lvalue_reference_v) && !decays_to && !decays_to; } FLUX_EXPORT template class optional; template requires std::is_object_v class optional { struct dummy {}; union { dummy dummy_{}; T item_; }; bool engaged_ = false; template constexpr auto construct(Args&&... args) { std::construct_at(std::addressof(item_), FLUX_FWD(args)...); engaged_ = true; } public: constexpr optional() noexcept {} constexpr explicit(false) optional(nullopt_t) noexcept {} template U = T> constexpr explicit optional(U&& item) noexcept(std::is_nothrow_constructible_v) : item_(FLUX_FWD(item)), engaged_(true) {} template requires std::constructible_from constexpr explicit optional(std::in_place_t, Args&&... args) noexcept(std::is_nothrow_constructible_v) : item_(FLUX_FWD(args)...), engaged_(true) {} /* * Destructors */ constexpr ~optional() { if (engaged_) { item_.T::~T(); } } ~optional() requires std::is_trivially_destructible_v = default; /* * Copy constructors */ constexpr optional(optional const& other) noexcept(std::is_nothrow_copy_constructible_v) requires std::copy_constructible { if (other.engaged_) { construct(other.item_); } } optional(optional const&) requires std::copy_constructible && std::is_trivially_constructible_v = default; /* * Copy-assignment operators */ constexpr optional& operator=(optional const& other) noexcept(std::is_nothrow_copy_assignable_v && std::is_nothrow_copy_constructible_v) requires std::copy_constructible { if (engaged_) { if (other.engaged_) { if constexpr (std::is_copy_assignable_v) { item_ = other.item_; } else { reset(); construct(other.item_); } } else { reset(); } } else { if (other.engaged_) { construct(other.item_); } } return *this; } optional& operator=(optional const&) requires std::copy_constructible && std::is_trivially_copy_assignable_v = default; /* * Move constructors */ constexpr optional(optional&& other) noexcept(std::is_nothrow_move_constructible_v) requires std::move_constructible { if (other.engaged_) { construct(std::move(other).item_); } } optional(optional&&) requires std::move_constructible && std::is_trivially_move_constructible_v = default; /* * Move-assignment operators */ constexpr optional& operator=(optional&& other) noexcept(std::is_nothrow_move_constructible_v && std::is_nothrow_move_assignable_v) requires std::move_constructible { if (engaged_) { if (other.engaged_) { if constexpr (std::is_move_assignable_v) { item_ = std::move(other).item_; } else { reset(); construct(std::move(other).item_); } } else { reset(); } } else { if (other.engaged_) { construct(std::move(other).item_); } } return *this; } constexpr optional& operator=(optional&&) requires std::move_constructible && std::is_trivially_move_assignable_v = default; /* * Observers */ [[nodiscard]] constexpr auto has_value() const -> bool { return engaged_; } constexpr explicit operator bool() const { return engaged_; } template Opt> [[nodiscard]] friend constexpr auto operator*(Opt&& self) -> decltype(auto) { if (!std::is_constant_evaluated()) { FLUX_ASSERT(self.has_value()); } return (FLUX_FWD(self).item_); } constexpr auto operator->() -> T* { if (!std::is_constant_evaluated()) { FLUX_ASSERT(this->has_value()); } return std::addressof(item_); } constexpr auto operator->() const -> T const* { if (!std::is_constant_evaluated()) { FLUX_ASSERT(this->has_value()); } return std::addressof(item_); } [[nodiscard]] constexpr auto value() & -> T& { return **this; } [[nodiscard]] constexpr auto value() const& -> T const& { return **this; } [[nodiscard]] constexpr auto value() && -> T&& { return *std::move(*this); } [[nodiscard]] constexpr auto value() const&& -> T const&& { return *std::move(*this); } [[nodiscard]] constexpr auto value_unchecked() & noexcept -> T& { return item_; } [[nodiscard]] constexpr auto value_unchecked() const& noexcept -> T const& { return item_; } [[nodiscard]] constexpr auto value_unchecked() && noexcept -> T&& { return std::move(item_); } [[nodiscard]] constexpr auto value_unchecked() const&& noexcept -> T const&& { return std::move(item_); } [[nodiscard]] constexpr auto value_or(auto&& alt) & -> decltype(has_value() ? value_unchecked() : FLUX_FWD(alt)) { return has_value() ? value_unchecked() : FLUX_FWD(alt); } [[nodiscard]] constexpr auto value_or(auto&& alt) const& -> decltype(has_value() ? value_unchecked() : FLUX_FWD(alt)) { return has_value() ? value_unchecked() : FLUX_FWD(alt); } [[nodiscard]] constexpr auto value_or(auto&& alt) && -> decltype(has_value() ? std::move(*this).value_unchecked() : FLUX_FWD(alt)) { return has_value() ? std::move(*this).value_unchecked() : FLUX_FWD(alt); } [[nodiscard]] constexpr auto value_or(auto&& alt) const&& -> decltype(has_value() ? std::move(*this).value_unchecked() : FLUX_FWD(alt)) { return has_value() ? std::move(*this).value_unchecked() : FLUX_FWD(alt); } private: template static constexpr auto do_compare(optional const& lhs, optional const& rhs, Cmp cmp) -> std::decay_t> { if (lhs.has_value() && rhs.has_value()) { return cmp(lhs.value_unchecked(), rhs.value_unchecked()); } else { return cmp(lhs.has_value(), rhs.has_value()); } } public: [[nodiscard]] friend constexpr auto operator==(optional const& lhs, optional const& rhs) -> bool requires std::equality_comparable { return do_compare(lhs, rhs, std::equal_to{}); } [[nodiscard]] friend constexpr auto operator<=>(optional const& lhs, optional const& rhs) requires std::totally_ordered && std::three_way_comparable { return do_compare(lhs, rhs, std::compare_three_way{}); } [[nodiscard]] friend constexpr auto operator<=>(optional const& lhs, optional const& rhs) requires std::totally_ordered { return do_compare(lhs, rhs, std::compare_partial_order_fallback); } [[nodiscard]] friend constexpr auto operator==(optional const& o, nullopt_t) -> bool { return !o.has_value(); } [[nodiscard]] friend constexpr auto operator<=>(optional const& o, nullopt_t) -> std::strong_ordering { return o.has_value() ? std::strong_ordering::greater : std::strong_ordering::equivalent; } /* * Modifiers */ constexpr auto reset() -> void { if (engaged_) { item_.T::~T(); engaged_ = false; } } template requires std::constructible_from constexpr auto emplace(Args&&... args) -> T& { reset(); construct(FLUX_FWD(args)...); return item_; } /* * Monadic operations */ template requires std::invocable && detail::can_optional> [[nodiscard]] constexpr auto map(F&& func) & -> optional> { using R = optional>; if (engaged_) { return R(std::invoke(FLUX_FWD(func), value_unchecked())); } else { return nullopt; } } template requires std::invocable && detail::can_optional> [[nodiscard]] constexpr auto map(F&& func) const& -> optional> { using R = optional>; if (engaged_) { return R(std::invoke(FLUX_FWD(func), value_unchecked())); } else { return nullopt; } } template requires std::invocable && detail::can_optional> [[nodiscard]] constexpr auto map(F&& func) && -> optional> { using R = optional>; if (engaged_) { return R(std::invoke(FLUX_FWD(func), std::move(*this).value_unchecked())); } else { return nullopt; } } template requires std::invocable && detail::can_optional> [[nodiscard]] constexpr auto map(F&& func) const&& -> optional> { using R = optional>; if (engaged_) { return R(std::invoke(FLUX_FWD(func), std::move(*this).value_unchecked())); } else { return nullopt; } } }; template optional(T) -> optional; template class optional { T* ptr_ = nullptr; static void test_fn(T&); public: optional() = default; constexpr explicit(false) optional(nullopt_t) noexcept {}; template requires requires(U& u) { test_fn(u); } constexpr explicit optional(U& item) noexcept : ptr_(std::addressof(item)) {} /* * Observers */ [[nodiscard]] constexpr auto has_value() const noexcept { return ptr_ != nullptr; } [[nodiscard]] constexpr explicit operator bool() const noexcept { return ptr_ != nullptr; } [[nodiscard]] constexpr auto operator*() const -> T& { if (!std::is_constant_evaluated()) { FLUX_ASSERT(ptr_ != nullptr); } return *ptr_; } constexpr auto operator->() const -> T* { if (!std::is_constant_evaluated()) { FLUX_ASSERT(ptr_ != nullptr); } return ptr_; } [[nodiscard]] constexpr auto value() const -> T& { return **this; } [[nodiscard]] constexpr auto value_unchecked() const noexcept -> T& { return *ptr_; } [[nodiscard]] constexpr auto value_or(auto&& alt) const -> decltype(has_value() ? value_unchecked() : FLUX_FWD(alt)) { return has_value() ? value_unchecked() : FLUX_FWD(alt); } [[nodiscard]] friend constexpr auto operator==(optional const& o, nullopt_t) -> bool { return !o.has_value(); } [[nodiscard]] friend constexpr auto operator<=>(optional const& o, nullopt_t) -> std::strong_ordering { return o.has_value() ? std::strong_ordering::greater : std::strong_ordering::equivalent; } /* * Modifiers */ constexpr auto reset() -> void { ptr_ = nullptr; } template requires requires(U& u) { test_fn(u); } constexpr auto emplace(U& item) -> void { ptr_ = std::addressof(item); } /* * Monadic operations */ template requires std::invocable && detail::can_optional> [[nodiscard]] constexpr auto map(F&& func) const -> optional> { using R = optional>; if (ptr_) { return R(std::invoke(FLUX_FWD(func), *ptr_)); } else { return nullopt; } } }; } // namespace flux #endif namespace flux { namespace detail { struct first_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq) const noexcept(noexcept(traits_t::first(seq))) -> cursor_t { return traits_t::first(seq); } }; struct is_last_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& cur) const noexcept(noexcept(traits_t::is_last(seq, cur))) -> bool { return traits_t::is_last(seq, cur); } }; struct read_at_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& cur) const noexcept(noexcept(traits_t::read_at(seq, cur))) -> element_t { return traits_t::read_at(seq, cur); } }; struct inc_fn { template constexpr auto operator()(Seq& seq, cursor_t& cur) const noexcept(noexcept(traits_t::inc(seq, cur))) -> cursor_t& { (void) traits_t::inc(seq, cur); return cur; } template constexpr auto operator()(Seq& seq, cursor_t& cur, distance_t offset) const noexcept(noexcept(traits_t::inc(seq, cur, offset))) -> cursor_t& { (void) traits_t::inc(seq, cur, offset); return cur; } }; struct dec_fn { template constexpr auto operator()(Seq& seq, cursor_t& cur) const noexcept(noexcept(traits_t::dec(seq, cur))) -> cursor_t& { (void) traits_t::dec(seq, cur); return cur; } }; struct distance_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& from, cursor_t const& to) const -> distance_t { if constexpr (random_access_sequence) { return traits_t::distance(seq, from, to); } else { distance_t n = 0; auto from_ = from; while (from_ != to) { inc_fn{}(seq, from_); ++n; } return n; } } }; struct data_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq) const noexcept(noexcept(traits_t::data(seq))) { return traits_t::data(seq); } }; struct last_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq) const noexcept(noexcept(traits_t::last(seq))) -> cursor_t { return traits_t::last(seq); } }; struct size_fn { template [[nodiscard]] constexpr auto operator()(Seq&& seq) const -> distance_t { if constexpr (requires { traits_t::size(seq); }) { return traits_t::size(seq); } else { static_assert(bounded_sequence && random_access_sequence); return distance_fn{}(seq, first_fn{}(seq), last_fn{}(seq)); } } }; struct usize_fn { template [[nodiscard]] constexpr auto operator()(Seq&& seq) const -> std::size_t { return checked_cast(size_fn{}(seq)); } }; template concept has_custom_move_at = sequence && requires (Seq& seq, cursor_t const& cur) { { traits_t::move_at(seq, cur) }; }; struct move_at_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& cur) const -> rvalue_element_t { if constexpr (has_custom_move_at) { return traits_t::move_at(seq, cur); } else { if constexpr (std::is_lvalue_reference_v>) { return std::move(read_at_fn{}(seq, cur)); } else { return read_at_fn{}(seq, cur); } } } }; template concept has_custom_read_at_unchecked = sequence && requires (Seq& seq, cursor_t const& cur) { { traits_t::read_at_unchecked(seq, cur) } -> std::same_as>; }; struct read_at_unchecked_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& cur) const -> element_t { if constexpr (has_custom_read_at_unchecked) { return traits_t::read_at_unchecked(seq, cur); } else { return read_at_fn{}(seq, cur); } } }; template concept has_custom_move_at_unchecked = sequence && requires (Seq& seq, cursor_t const& cur) { { traits_t::move_at_unchecked(seq, cur) } -> std::same_as>; }; struct move_at_unchecked_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t const& cur) const -> rvalue_element_t { if constexpr (has_custom_move_at_unchecked) { return traits_t::move_at_unchecked(seq, cur); } else if constexpr (has_custom_move_at) { return move_at_fn{}(seq, cur); } else if constexpr (std::is_lvalue_reference_v>){ return std::move(read_at_unchecked_fn{}(seq, cur)); } else { return read_at_unchecked_fn{}(seq, cur); } } }; } // namespace detail FLUX_EXPORT inline constexpr auto first = detail::first_fn{}; FLUX_EXPORT inline constexpr auto is_last = detail::is_last_fn{}; FLUX_EXPORT inline constexpr auto read_at = detail::read_at_fn{}; FLUX_EXPORT inline constexpr auto move_at = detail::move_at_fn{}; FLUX_EXPORT inline constexpr auto read_at_unchecked = detail::read_at_unchecked_fn{}; FLUX_EXPORT inline constexpr auto move_at_unchecked = detail::move_at_unchecked_fn{}; FLUX_EXPORT inline constexpr auto inc = detail::inc_fn{}; FLUX_EXPORT inline constexpr auto dec = detail::dec_fn{}; FLUX_EXPORT inline constexpr auto distance = detail::distance_fn{}; FLUX_EXPORT inline constexpr auto data = detail::data_fn{}; FLUX_EXPORT inline constexpr auto last = detail::last_fn{}; FLUX_EXPORT inline constexpr auto size = detail::size_fn{}; FLUX_EXPORT inline constexpr auto usize = detail::usize_fn{}; namespace detail { struct next_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t cur) const noexcept(noexcept(inc(seq, cur))) -> cursor_t { return inc(seq, cur); } template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t cur, distance_t offset) const -> cursor_t { if constexpr (random_access_sequence) { return inc(seq, cur, offset); } else if constexpr (bidirectional_sequence) { auto const zero = distance_t{0}; if (offset > zero) { while (offset-- > zero) { inc(seq, cur); } } else { while (offset++ < zero) { dec(seq, cur); } } return cur; } else { while (offset-- > distance_t{0}) { inc(seq, cur); } return cur; } } }; struct prev_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq, cursor_t cur) const noexcept(noexcept(dec(seq, cur))) -> cursor_t { return dec(seq, cur); } }; struct is_empty_fn { template requires (multipass_sequence || sized_sequence) [[nodiscard]] constexpr auto operator()(Seq&& seq) const -> bool { if constexpr (sized_sequence) { return flux::size(seq) == 0; } else { return is_last(seq, first(seq)); } } }; template concept element_swappable_with_ = std::constructible_from, rvalue_element_t> && writable_sequence_of> && writable_sequence_of&&>; template concept element_swappable_with = element_swappable_with_ && element_swappable_with_; struct swap_with_fn { template constexpr void operator()(Seq1& seq1, cursor_t const& cur1, Seq2& seq2, cursor_t const& cur2) const requires (std::swappable_with, element_t> || element_swappable_with) { if constexpr (std::swappable_with, element_t>) { return std::ranges::swap(read_at(seq1, cur1), read_at(seq2, cur2)); } else { value_t temp(move_at(seq1, cur1)); read_at(seq1, cur1) = move_at(seq2, cur2); read_at(seq2, cur2) = std::move(temp); } } }; struct swap_at_fn { template constexpr void operator()(Seq& seq, cursor_t const& first, cursor_t const& second) const requires requires { swap_with_fn{}(seq, first, seq, second); } { return swap_with_fn{}(seq, first, seq, second); } }; struct front_fn { template [[nodiscard]] constexpr auto operator()(Seq& seq) const -> optional> { auto cur = first(seq); if (!is_last(seq, cur)) { return optional>(read_at(seq, cur)); } else { return nullopt; } } }; struct back_fn { template requires bounded_sequence [[nodiscard]] constexpr auto operator()(Seq& seq) const -> optional> { auto cur = last(seq); if (cur != first(seq)) { return optional>(read_at(seq, dec(seq, cur))); } else { return nullopt; } } }; } // namespace detail FLUX_EXPORT inline constexpr auto next = detail::next_fn{}; FLUX_EXPORT inline constexpr auto prev = detail::prev_fn{}; FLUX_EXPORT inline constexpr auto is_empty = detail::is_empty_fn{}; FLUX_EXPORT inline constexpr auto swap_with = detail::swap_with_fn{}; FLUX_EXPORT inline constexpr auto swap_at = detail::swap_at_fn{}; FLUX_EXPORT inline constexpr auto front = detail::front_fn{}; FLUX_EXPORT inline constexpr auto back = detail::back_fn{}; } // namespace flux #endif #include #include namespace flux { /* * Default implementation for C arrays of known bound */ template struct sequence_traits { static constexpr auto first(auto const&) -> index_t { return index_t{0}; } static constexpr bool is_last(auto const&, index_t idx) { return idx >= N; } static constexpr auto read_at(auto& self, index_t idx) -> decltype(auto) { indexed_bounds_check(idx, N); return self[idx]; } static constexpr auto read_at_unchecked(auto& self, index_t idx) -> decltype(auto) { return self[idx]; } static constexpr auto inc(auto const&, index_t& idx) { FLUX_DEBUG_ASSERT(idx < N); idx = num::checked_add(idx, distance_t{1}); } static constexpr auto last(auto const&) -> index_t { return N; } static constexpr auto dec(auto const&, index_t& idx) { FLUX_DEBUG_ASSERT(idx > 0); idx = num::checked_sub(idx, distance_t{1}); } static constexpr auto inc(auto const&, index_t& idx, distance_t offset) { FLUX_DEBUG_ASSERT(num::checked_add(idx, offset) <= N); FLUX_DEBUG_ASSERT(num::checked_add(idx, offset) >= 0); idx = num::checked_add(idx, offset); } static constexpr auto distance(auto const&, index_t from, index_t to) -> distance_t { return num::checked_sub(to, from); } static constexpr auto data(auto& self) -> auto* { return self; } static constexpr auto size(auto const&) -> distance_t { return N; } static constexpr auto for_each_while(auto& self, auto&& pred) -> index_t { index_t idx = 0; while (idx < N) { if (!std::invoke(pred, self[idx])) { break; } ++idx; } return idx; } }; /* * Default implementation for std::reference_wrapper */ template struct sequence_traits> { using self_t = std::reference_wrapper; using value_type = value_t; static constexpr bool disable_multipass = !multipass_sequence; static constexpr auto first(self_t self) -> cursor_t { return flux::first(self.get()); } static constexpr bool is_last(self_t self, cursor_t const& cur) { return flux::is_last(self.get(), cur); } static constexpr auto read_at(self_t self, cursor_t const& cur) -> decltype(auto) { return flux::read_at(self.get(), cur); } static constexpr auto read_at_unchecked(self_t self, cursor_t const& cur) -> decltype(auto) { return flux::read_at_unchecked(self.get(), cur); } static constexpr auto inc(self_t self, cursor_t& cur) -> cursor_t& { return flux::inc(self.get(), cur); } static constexpr auto dec(self_t self, cursor_t& cur) -> cursor_t& requires bidirectional_sequence { return flux::dec(self.get(), cur); } static constexpr auto inc(self_t self, cursor_t& cur, distance_t offset) -> cursor_t& requires random_access_sequence { return flux::inc(self.get(), cur, offset); } static constexpr auto distance(self_t self, cursor_t const& from, cursor_t const& to) -> distance_t requires random_access_sequence { return flux::distance(self.get(), from, to); } static constexpr auto data(self_t self) requires contiguous_sequence { return flux::data(self.get()); } static constexpr auto last(self_t self) -> cursor_t requires bounded_sequence { return flux::last(self.get()); } static constexpr auto size(self_t self) -> distance_t requires sized_sequence { return flux::size(self.get()); } static constexpr auto move_at(self_t self, cursor_t const& cur) -> rvalue_element_t { return flux::move_at(self.get(), cur); } }; // Default implementation for contiguous, sized ranges template requires (!detail::derived_from_inline_sequence_base && std::ranges::contiguous_range && std::ranges::sized_range && std::ranges::contiguous_range && std::ranges::sized_range) struct sequence_traits { using value_type = std::ranges::range_value_t; static constexpr auto first(auto&) -> index_t { return index_t{0}; } static constexpr auto is_last(auto& self, index_t idx) { return idx >= size(self); } static constexpr auto inc(auto& self, index_t& idx) { FLUX_DEBUG_ASSERT(idx < size(self)); idx = num::checked_add(idx, distance_t{1}); } static constexpr auto read_at(auto& self, index_t idx) -> decltype(auto) { indexed_bounds_check(idx, size(self)); return data(self)[idx]; } static constexpr auto read_at_unchecked(auto& self, index_t idx) -> decltype(auto) { return data(self)[idx]; } static constexpr auto dec(auto&, index_t& idx) { FLUX_DEBUG_ASSERT(idx > 0); idx = num::checked_sub(idx, distance_t{1}); } static constexpr auto last(auto& self) -> index_t { return size(self); } static constexpr auto inc(auto& self, index_t& idx, distance_t offset) { FLUX_DEBUG_ASSERT(num::checked_add(idx, offset) <= size(self)); FLUX_DEBUG_ASSERT(num::checked_add(idx, offset) >= 0); idx = num::checked_add(idx, offset); } static constexpr auto distance(auto&, index_t from, index_t to) -> distance_t { return num::checked_sub(to, from); } static constexpr auto size(auto& self) -> distance_t { return checked_cast(std::ranges::ssize(self)); } static constexpr auto data(auto& self) -> auto* { return std::ranges::data(self); } static constexpr auto for_each_while(auto& self, auto&& pred) -> index_t { auto iter = std::ranges::begin(self); auto const end = std::ranges::end(self); while (iter != end) { if (!std::invoke(pred, *iter)) { break; } ++iter; } return checked_cast(iter - std::ranges::begin(self)); } }; } // namespace flux #endif // FLUX_CORE_DEFAULT_IMPLS_HPP_INCLUDED // Copyright (c) 2023 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_FUNCTIONAL_HPP_INCLUDED #define FLUX_CORE_FUNCTIONAL_HPP_INCLUDED #include #include namespace flux { FLUX_EXPORT template struct proj { Fn fn; Proj prj{}; template constexpr auto operator()(Args&&... args) noexcept(noexcept(std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...))) -> decltype(std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...)) { return std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...); } template constexpr auto operator()(Args&&... args) const noexcept(noexcept(std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...))) -> decltype(std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...)) { return std::invoke(fn, std::invoke(prj, FLUX_FWD(args))...); } }; template proj(F, P = {}) -> proj; FLUX_EXPORT template struct proj2 { Fn fn; Lhs lhs{}; Rhs rhs{}; template constexpr auto operator()(Arg1&& arg1, Arg2&& arg2) noexcept(noexcept(std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2))))) -> decltype(std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2)))) { return std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2))); } template constexpr auto operator()(Arg1&& arg1, Arg2&& arg2) const noexcept(noexcept(std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2))))) -> decltype(std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2)))) { return std::invoke(fn, std::invoke(lhs, FLUX_FWD(arg1)), std::invoke(rhs, FLUX_FWD(arg2))); } }; template proj2(F, L = {}, R = {}) -> proj2; namespace detail { template struct lazy_apply { Func func_; template constexpr auto operator()(Tuple&& tuple) & noexcept(noexcept(std::apply(func_, FLUX_FWD(tuple)))) -> decltype(std::apply(func_, FLUX_FWD(tuple))) { return std::apply(func_, FLUX_FWD(tuple)); } template constexpr auto operator()(Tuple&& tuple) const& noexcept(noexcept(std::apply(func_, FLUX_FWD(tuple)))) -> decltype(std::apply(func_, FLUX_FWD(tuple))) { return std::apply(func_, FLUX_FWD(tuple)); } template constexpr auto operator()(Tuple&& tuple) && noexcept(noexcept(std::apply(std::move(func_), FLUX_FWD(tuple)))) -> decltype(std::apply(std::move(func_), FLUX_FWD(tuple))) { return std::apply(std::move(func_), FLUX_FWD(tuple)); } template constexpr auto operator()(Tuple&& tuple) const&& noexcept(noexcept(std::apply(std::move(func_), FLUX_FWD(tuple)))) -> decltype(std::apply(std::move(func_), FLUX_FWD(tuple))) { return std::apply(std::move(func_), FLUX_FWD(tuple)); } }; struct unpack_fn { template constexpr auto operator()(Func&& func) const -> lazy_apply> { return lazy_apply>{.func_ = FLUX_FWD(func)}; } }; } // namespace detail FLUX_EXPORT inline constexpr auto unpack = detail::unpack_fn{}; namespace pred { namespace detail { template struct predicate : Lambda {}; template predicate(L) -> predicate; template inline constexpr auto cmp = [](auto&& val) { return predicate{[val = FLUX_FWD(val)](auto const& other) { return Op{}(other, val); }}; }; } // namespace detail /// Given a predicate, returns a new predicate with the condition reversed FLUX_EXPORT inline constexpr auto not_ = [](auto&& pred) { return detail::predicate([p = FLUX_FWD(pred)] (auto const&... args) { return !std::invoke(p, FLUX_FWD(args)...); }); }; /// Returns a new predicate which is satisifed only if both the given predicates /// return `true`. /// /// The returned predicate is short-circuiting: if the first predicate returns /// `false`, the second will not be evaluated. FLUX_EXPORT inline constexpr auto both = [](auto&& p, auto&& and_) { return detail::predicate{[p1 = FLUX_FWD(p), p2 = FLUX_FWD(and_)] (auto const&... args) { return std::invoke(p1, args...) && std::invoke(p2, args...); }}; }; /// Returns a new predicate which is satisfied only if either of the given /// predicates return `true`. /// /// The returned predicate is short-circuiting: if the first predicate returns /// `true`, the second will not be evaluated FLUX_EXPORT inline constexpr auto either = [](auto&& p, auto&& or_) { return detail::predicate{[p1 = FLUX_FWD(p), p2 = FLUX_FWD(or_)] (auto const&... args) { return std::invoke(p1, args...) || std::invoke(p2, args...); }}; }; namespace detail { FLUX_EXPORT template constexpr auto operator!(detail::predicate

pred) { return not_(std::move(pred)); } FLUX_EXPORT template constexpr auto operator&&(detail::predicate lhs, detail::predicate rhs) { return both(std::move(lhs), std::move(rhs)); } FLUX_EXPORT template constexpr auto operator||(detail::predicate lhs, detail::predicate rhs) { return either(std::move(lhs), std::move(rhs)); } } // namespace detail /// Returns a new predicate with is satified only if both of the given /// predicates return `false`. /// /// The returned predicate is short-circuiting: if the first predicate returns /// `true`, the second will not be evaluated. FLUX_EXPORT inline constexpr auto neither = [](auto&& p1, auto&& nor) { return not_(either(FLUX_FWD(p1), FLUX_FWD(nor))); }; FLUX_EXPORT inline constexpr auto eq = detail::cmp; FLUX_EXPORT inline constexpr auto neq = detail::cmp; FLUX_EXPORT inline constexpr auto lt = detail::cmp; FLUX_EXPORT inline constexpr auto gt = detail::cmp; FLUX_EXPORT inline constexpr auto leq = detail::cmp; FLUX_EXPORT inline constexpr auto geq = detail::cmp; /// A predicate which always returns true FLUX_EXPORT inline constexpr auto true_ = detail::predicate{[](auto const&...) -> bool { return true; }}; /// A predicate which always returns false FLUX_EXPORT inline constexpr auto false_ = detail::predicate{[](auto const&...) -> bool { return false; }}; /// Identity predicate, returns the boolean value given to it FLUX_EXPORT inline constexpr auto id = detail::predicate{[](bool b) -> bool { return b; }}; /// Returns true if the given value is greater than a zero of the same type. FLUX_EXPORT inline constexpr auto positive = detail::predicate{[](auto const& val) -> bool { return val > decltype(val){0}; }}; /// Returns true if the given value is less than a zero of the same type. FLUX_EXPORT inline constexpr auto negative = detail::predicate{[](auto const& val) -> bool { return val < decltype(val){0}; }}; /// Returns true if the given value is not equal to a zero of the same type. FLUX_EXPORT inline constexpr auto nonzero = detail::predicate{[](auto const& val) -> bool { return val != decltype(val){0}; }}; /// Given a sequence of values, constructs a predicate which returns true /// if its argument compares equal to one of the values FLUX_EXPORT inline constexpr auto in = [](auto const&... vals) requires (sizeof...(vals) > 0) { return detail::predicate{[vals...](auto const& arg) -> bool { return ((arg == vals) || ...); }}; }; FLUX_EXPORT inline constexpr auto even = detail::predicate([](auto const& val) -> bool { return val % decltype(val){2} == decltype(val){0}; }); FLUX_EXPORT inline constexpr auto odd = detail::predicate([](auto const& val) -> bool { return val % decltype(val){2} != decltype(val){0}; }); } // namespace pred namespace cmp { namespace detail { struct min_fn { template requires std::strict_weak_order [[nodiscard]] constexpr auto operator()(T&& t, U&& u, Cmp cmp = Cmp{}) const -> std::common_reference_t { return std::invoke(cmp, u, t) ? FLUX_FWD(u) : FLUX_FWD(t); } }; struct max_fn { template requires std::strict_weak_order [[nodiscard]] constexpr auto operator()(T&& t, U&& u, Cmp cmp = Cmp{}) const -> std::common_reference_t { return !std::invoke(cmp, u, t) ? FLUX_FWD(u) : FLUX_FWD(t); } }; } // namespace detail FLUX_EXPORT inline constexpr auto min = detail::min_fn{}; FLUX_EXPORT inline constexpr auto max = detail::max_fn{}; } // namespace cmp } // namespace flux #endif // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_CORE_INLINE_SEQUENCE_BASE_HPP_INCLUDED #define FLUX_CORE_INLINE_SEQUENCE_BASE_HPP_INCLUDED // Copyright (c) 2022 Tristan Brindle (tcbrindle at gmail dot com) // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef FLUX_OP_REQUIREMENTS_HPP_INCLUDED #define FLUX_OP_REQUIREMENTS_HPP_INCLUDED namespace flux { FLUX_EXPORT template using fold_result_t = std::decay_t>>; namespace detail { template > concept foldable_ = std::invocable> && std::convertible_to && std::assignable_from>>; } // namespace detail namespace detail { template struct repeated_invocable_helper { template using repeater = E; static inline constexpr bool value = [] (std::index_sequence) consteval { return std::regular_invocable...>; }(std::make_index_sequence{}); }; template concept repeated_invocable = repeated_invocable_helper::value; } // namespace detail FLUX_EXPORT template concept foldable = sequence && std::invocable> && detail::foldable_; FLUX_EXPORT template concept strict_weak_order_for = sequence && sequence && std::strict_weak_order, element_t> && std::strict_weak_order&, element_t> && std::strict_weak_order, value_t&> && std::strict_weak_order&, value_t&> && std::strict_weak_order, common_element_t>; } // namespace flux #endif // FLUX_OP_REQUIREMENTS_HPP_INCLUDED namespace flux { FLUX_EXPORT template struct bounds { FLUX_NO_UNIQUE_ADDRESS Cur from; FLUX_NO_UNIQUE_ADDRESS Cur to; friend bool operator==(bounds const&, bounds const&) = default; }; template bounds(Cur, Cur) -> bounds; FLUX_EXPORT template using bounds_t = bounds>; template struct inline_sequence_base { private: constexpr auto derived() -> Derived& { return static_cast(*this); } constexpr auto derived() const -> Derived const& { return static_cast(*this); } public: /* * Basic iteration functions */ /// Returns a cursor pointing to the first element of the sequence [[nodiscard]] constexpr auto first() { return flux::first(derived()); } /// Returns true if `cur` points to the end of the sequence /// /// @param cur The cursor to test template D = Derived> [[nodiscard]] constexpr bool is_last(cursor_t const& cur) { return flux::is_last(derived(), cur); } /// Increments the given cursor /// /// @param cur the cursor to increment template D = Derived> constexpr auto& inc(cursor_t& cur) { return flux::inc(derived(), cur); } /// Returns the element at the given cursor template D = Derived> [[nodiscard]] constexpr decltype(auto) read_at(cursor_t const& cur) { return flux::read_at(derived(), cur); } /// Returns an rvalue version of the element at the given cursor template D = Derived> [[nodiscard]] constexpr decltype(auto) move_at(cursor_t const& cur) { return flux::move_at(derived(), cur); } /// Returns the element at the given cursor template D = Derived> [[nodiscard]] constexpr decltype(auto) operator[](cursor_t const& cur) { return flux::read_at(derived(), cur); } /// Returns an cursor pointing to one past the last element of the sequence [[nodiscard]] constexpr auto last() requires bounded_sequence { return flux::last(derived()); } /// Decrements the given cursor template D = Derived> requires bidirectional_sequence constexpr auto& dec(cursor_t& cur) { return flux::dec(derived(), cur); } /// Increments the given cursor by `offset` places template D = Derived> requires random_access_sequence constexpr auto& inc(cursor_t& cur, distance_t offset) { return flux::inc(derived(), cur, offset); } /// Returns the number of times `from` must be incremented to reach `to` /// /// For a random-access sequence, returns the result in constant time template D = Derived> requires multipass_sequence [[nodiscard]] constexpr auto distance(cursor_t const& from, cursor_t const& to) { return flux::distance(derived(), from, to); } [[nodiscard]] constexpr auto data() requires contiguous_sequence { return flux::data(derived()); } [[nodiscard]] constexpr auto data() const requires contiguous_sequence { return flux::data(derived()); } /// Returns the number of elements in the sequence [[nodiscard]] constexpr auto size() requires sized_sequence { return flux::size(derived()); } [[nodiscard]] constexpr auto size() const requires sized_sequence { return flux::size(derived()); } /// Returns the number of elements in the sequence as a size_t [[nodiscard]] constexpr auto usize() requires sized_sequence { return flux::usize(derived()); } [[nodiscard]] constexpr auto usize() const requires sized_sequence { return flux::usize(derived()); } /// Returns true if the sequence contains no elements [[nodiscard]] constexpr auto is_empty() requires (multipass_sequence || sized_sequence) { return flux::is_empty(derived()); } template D = Derived> [[nodiscard]] constexpr auto next(cursor_t cur) { return flux::next(derived(), cur); } template D = Derived> requires bidirectional_sequence [[nodiscard]] constexpr auto prev(cursor_t cur) { return flux::prev(derived(), cur); } [[nodiscard]] constexpr auto front() requires multipass_sequence { return flux::front(derived()); } [[nodiscard]] constexpr auto front() const requires multipass_sequence { return flux::front(derived()); } [[nodiscard]] constexpr auto back() requires bidirectional_sequence && bounded_sequence { return flux::back(derived()); } [[nodiscard]] constexpr auto back() const requires bidirectional_sequence && bounded_sequence { return flux::back(derived()); } template requires std::invocable constexpr auto _(Func&& func, Args&&... args) & -> decltype(auto) { return std::invoke(FLUX_FWD(func), derived(), FLUX_FWD(args)...); } template requires std::invocable constexpr auto _(Func&& func, Args&&... args) const& -> decltype(auto) { return std::invoke(FLUX_FWD(func), derived(), FLUX_FWD(args)...); } template requires std::invocable constexpr auto _(Func&& func, Args&&... args) && -> decltype(auto) { return std::invoke(FLUX_FWD(func), std::move(derived()), FLUX_FWD(args)...); } template requires std::invocable constexpr auto _(Func&& func, Args&&... args) const&& -> decltype(auto) { return std::invoke(FLUX_FWD(func), std::move(derived()), FLUX_FWD(args)...); } constexpr auto ref() const& requires const_iterable_sequence; auto ref() const&& -> void = delete; constexpr auto mut_ref() &; /* * Iterator support */ constexpr auto begin() &; constexpr auto begin() const& requires sequence; constexpr auto end() &; constexpr auto end() const& requires sequence; /* * Adaptors */ template [[nodiscard]] constexpr auto adjacent() && requires multipass_sequence; template requires multipass_sequence && std::predicate, element_t> [[nodiscard]] constexpr auto adjacent_filter(Pred pred) &&; template requires multipass_sequence [[nodiscard]] constexpr auto adjacent_map(Func func) &&; [[nodiscard]] constexpr auto cache_last() && requires bounded_sequence || (multipass_sequence && not infinite_sequence); [[nodiscard]] constexpr auto chunk(std::integral auto chunk_sz) &&; template requires multipass_sequence && std::predicate, element_t> [[nodiscard]] constexpr auto chunk_by(Pred pred) &&; [[nodiscard]] constexpr auto cursors() && requires multipass_sequence; [[nodiscard]] constexpr auto cycle() && requires infinite_sequence || multipass_sequence; [[nodiscard]] constexpr auto cycle(std::integral auto count) && requires multipass_sequence; [[nodiscard]] constexpr auto dedup() && requires multipass_sequence && std::equality_comparable>; [[nodiscard]] constexpr auto drop(std::integral auto count) &&; template requires std::predicate> [[nodiscard]] constexpr auto drop_while(Pred pred) &&; template requires std::predicate> [[nodiscard]] constexpr auto filter(Pred pred) &&; [[nodiscard]] constexpr auto flatten() && requires sequence>; template requires std::invocable> [[nodiscard]] constexpr auto map(Func func) &&; template requires detail::boolean_testable> [[nodiscard]] constexpr auto mask(Mask&& mask_) &&; [[nodiscard]] constexpr auto pairwise() && requires multipass_sequence; template requires multipass_sequence [[nodiscard]] constexpr auto pairwise_map(Func func) &&; template requires foldable [[nodiscard]] constexpr auto prescan(Func func, Init init) &&; [[nodiscard]] constexpr auto read_only() &&; [[nodiscard]] constexpr auto reverse() && requires bidirectional_sequence && bounded_sequence; template > requires foldable [[nodiscard]] constexpr auto scan(Func func, Init init = Init{}) &&; template requires foldable> [[nodiscard]] constexpr auto scan_first(Func func) &&; [[nodiscard]] constexpr auto slide(std::integral auto win_sz) && requires multipass_sequence; template requires multipass_sequence && multipass_sequence && std::equality_comparable_with, element_t> [[nodiscard]] constexpr auto split(Pattern&& pattern) &&; template requires multipass_sequence && std::equality_comparable_with, Delim const&> [[nodiscard]] constexpr auto split(Delim&& delim) &&; template requires multipass_sequence && std::predicate> [[nodiscard]] constexpr auto split(Pred pred) &&; template [[nodiscard]] constexpr auto split_string(Pattern&& pattern) &&; [[nodiscard]] constexpr auto stride(std::integral auto by) &&; [[nodiscard]] constexpr auto take(std::integral auto count) &&; template requires std::predicate> [[nodiscard]] constexpr auto take_while(Pred pred) &&; /* * Algorithms */ /// Returns `true` if every element of the sequence satisfies the predicate template requires std::predicate> [[nodiscard]] constexpr auto all(Pred pred); template requires std::predicate> [[nodiscard]] constexpr auto any(Pred pred); template requires std::equality_comparable_with, Value const&> constexpr auto contains(Value const& value) -> bool; /// Returns the number of elements in the sequence constexpr auto count(); /// Returns the number of elements in the sequence which are equal to `value` template requires std::equality_comparable_with, Value const&> constexpr auto count_eq(Value const& value); template requires std::predicate> constexpr auto count_if(Pred pred); template requires std::predicate, element_t> && (multipass_sequence || sized_sequence) && (multipass_sequence || sized_sequence) constexpr auto ends_with(Needle&& needle, Cmp cmp = {}) -> bool; template requires writable_sequence_of constexpr auto fill(Value const& value) -> void; /// Returns a cursor pointing to the first occurrence of `value` in the sequence template requires std::equality_comparable_with, Value const&> [[nodiscard]] constexpr auto find(Value const&); template requires std::predicate> [[nodiscard]] constexpr auto find_if(Pred pred); template requires std::predicate> [[nodiscard]] constexpr auto find_if_not(Pred pred); template requires strict_weak_order_for [[nodiscard]] constexpr auto find_max(Cmp cmp = Cmp{}); template requires strict_weak_order_for [[nodiscard]] constexpr auto find_min(Cmp cmp = Cmp{}); template requires strict_weak_order_for [[nodiscard]] constexpr auto find_minmax(Cmp cmp = Cmp{}); template requires foldable [[nodiscard]] constexpr auto fold(Func func, Init init) -> fold_result_t; template requires std::invocable, element_t> && std::assignable_from&, std::invoke_result_t, element_t>> [[nodiscard]] constexpr auto fold_first(Func func); template requires std::invocable> constexpr auto for_each(Func func) -> Func; template requires std::invocable> && detail::boolean_testable>> constexpr auto for_each_while(Pred pred); constexpr auto inplace_reverse() requires bounded_sequence && detail::element_swappable_with; template requires strict_weak_order_for constexpr auto max(Cmp cmp = Cmp{}); template requires strict_weak_order_for constexpr auto min(Cmp cmp = Cmp{}); template requires strict_weak_order_for constexpr auto minmax(Cmp cmp = Cmp{}); template requires std::predicate> [[nodiscard]] constexpr auto none(Pred pred); template requires std::weakly_incrementable && std::indirectly_writable> constexpr auto output_to(Iter iter) -> Iter; constexpr auto sum() requires foldable, value_t> && std::default_initializable>; template requires random_access_sequence && bounded_sequence && detail::element_swappable_with && strict_weak_order_for constexpr void sort(Cmp cmp = {}); constexpr auto product() requires foldable, value_t> && requires { value_t(1); }; template requires std::predicate, element_t> constexpr auto starts_with(Needle&& needle, Cmp cmp = Cmp{}) -> bool; template constexpr auto to(Args&&... args) -> Container; template