tcbrindle / flux Goto Github PK

The CPPNorth talk got me excited with the filter analysis thing, but it seems even in flux, the use of filter prevents auto-vectorization.
https://flux.godbolt.org/z/qjr85c4aY Here we can see that the imperative code vectorizes normally but not the flux code. There is the same problem with the stdlib range view adaptors.

Below is a comparison with Rust to show that this kind of things should be possible. My understanding of the issue is that filter being non-shape preserving is what prevents vectorization, but I thought the filter consumer analysis would help with that.

I believe there might be a way to make it work by having the filter adaptor return some optionals instead of changing the shape of the sequence. Thoughts?

Why is iota hidden in <flux/source/*>? Other views are in <flux/op/*>.

In this issue, I suggest adding compress sequence adaptor.

Compress adaptor filters elements from the input sequence, returning only those that have a corresponding element in selectors that evaluates to true. Stops when either the input sequence or selectors sequences has been exhausted. Roughly equivalent to:

flux::generator compress(seq, selectors) {
    // compress("ABCDEF", {1,0,1,0,1,1}) --> A C E F
    for (auto [v, s]: flux::zip(seq, selectors)) {
        if (s) {
            co_yield v;
        }
    }
}

map_adaptor doesn't provide a specialisation of read_at_unchecked(), meaning that anyone requesting an unchecked read on a mapped sequence is going to end up getting a checked read on the underlying sequence and possibly less optimal code than they wanted.

Non const-iterable reversed sequences are pretty rare, but if you find one and try to use it in a range-for loop (or anything else that calls member begin()) it will hard error.

This is because in checking the constraints for begin() const, it tries to check the return type of sequence_traits<reverse_adaptor>::read_at which returns decltype(auto), meaning the compiler will instantiate the function to find out the return type. Unfortunately, the body of this function calls flux::prev, which then hard errors.

There are a couple of possible solutions, but the easiest is probably to avoid decltype(auto) and instead use decltype(<actual expression>) so we get graceful return type SFINAE.

This is pretty much the same as #47, but with reverse_adaptor rather than zip_adaptor.

Currently filter_adaptor uses the same cursor type as its parent sequence, unmodified. This works fine, but can lead to odd situations where using a parent cursor (such as an integer index for a vector, say) on the filtered sequence appears to "ignore" the filter:

std::vector vals{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

auto filtered = flux::ref(vals).filter(flux::pred::even);

std::cout << filtered[0] << std::endl; // prints 1 ?!

Godbolt

To avoid this, filter_adaptor should wrap its underlying cursor as something like

struct cursor_type {
    cursor_t<Base> base_cur;
};

to turn the last line above into a compile error.

Thought I'd follow up my last question with another question.

I see that in flux, filter's implementation of first just does a find_if:

So is the intent that there is no complexity requirement on first (and potentially last and is_last)?

My go-to example for the complexity requirements in Ranges is r.drop_last_while(p).stride(2), but in flux actually I think it's enough to ask about r.drop_last_while(p) even by itself (which flux doesn't have yet, but don't treat this as a request to go rush to add it). If the flux::is_last check is going to be implemented as a find_if (or, whatever, find_last_if_not) then iterating over this sequence becomes quadratic time:

Hi, I was recently trying to run flux on clang, this can be easily replicated by visiting https://flux.godbolt.org/ and using clang trunk which I assume is 18.1.0 (https://flux.godbolt.org/z/6x7G8n6G1) but the stacktrace is here for Clang 19 experimental build if anyone is interested.

I am not sure if this is clang issue or flux but I hope this get resolved soon enough.

It looks like the CodeQL workflow isn't working properly, reporting a configuration error: https://github.com/tcbrindle/flux/security/code-scanning/tools/CodeQL/status

The workflow is still running for PRs and there's nothing obvious in the logs to indicate anything is amiss, so I'll have to investigate

I'm trying to build the flux library tests and benchmarks and am running into some issues with the precompiled headers. When I try to build test-libflux, I get the following output error message:

C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.36.32532\modules\std.ixx(147,1): Error C1010 fatal : unexpected end of file while looking for precompiled header. Did you forget to add '#include "D:/Repositories/flux/build/test/CMakeFiles/test-libflux.dir/Debug/cmake_pch.hxx"' to your source?

But based on the documentation my understanding is that you don't need to explicitly include the pre-compiled header. Am I doing something wrong?

As already stated in the issue #126, there are some configuration issues. Building on msvc (as cmake project) is fine, but when I do remote compiling on my ubuntu runner, a similar error appears.

CMake Error in build/_deps/flux-src/CMakeLists.txt:
  Target "flux" INTERFACE_SOURCES property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the build directory.


CMake Error in build/_deps/flux-src/CMakeLists.txt:
  Target "flux" INTERFACE_SOURCES property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the build directory.Target "flux" INTERFACE_SOURCES
  property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the source directory.

Going back the history, it seems that a00f83b introduces the error for me. Until then, everything works fine.

C++23 adds std::views::join_with, which takes a range-of-ranges and a pattern and produces the elements of the inner ranges with the pattern interspersed.

We should have it too.

As always though, naming is hard. Our version of views::join is called flatten, to avoid the confusion that occurs in the ranges world between views::join (which takes a range-of-ranges) and views::concat (which takes a variadic pack of ranges and glues them together). So we could call our version flatten_with, following the same pattern. On the other hand, Range-V3 (unlike C++23) instead provides a second overload of views::join which takes an extra parameter. We could do the same and provide another overload of flatten, although I'm not particularly keen on that.

Another option could be to name our version of the adaptor just join, as it performs the opposite action to split: that is, seq.split(pattern).join(pattern) and seq_of_seqs.join(pattern).split(pattern) should each end up as a long-winded round-trip. Split and join as the complement of each other seems pretty nice, but it does again raise the possibility of join being mixed up with chain (our version of views::concat).

Yet another option could be intersperse or interleave, although either name seems more like it should take a pair (or pack?) of sequences and alternate between an element of the first sequence and an element of the second sequence until one is exhausted.

(D provides roundRobin(), which takes a variadic number of ranges and produces elements of each in turn until all are exhausted, which is a slightly different algorithm -- though I like that one too.)

Been playing around with flux and noticed that the generated code had checks for safe std::variant access, even though the logic ensures that it was safe. I've identified a few places in the code, but there are more patterns like this: igrekster@70ef410

Here is before/after on the Compiler Explorer: https://godbolt.org/z/azfqMbT5j

And a Rust equivalent to compare: https://rust.compiler-explorer.com/z/K6E5xYc3W

I came here from your recent talk "A Safer Iteration Model for C++ - Tristan Brindle - C++ on Sea 2023", and generally I like it. 😎

The naming of is_last though is confusing because it's not testing whether the current points to the last thing, but rather whether it points after the last thing. The name first is fine for the starting point, but for the stopping point, you really want to know whether the cursor is at the limit (like limits in math, an element one past which is not actually ever reached). I considered possible alternate names 🤔:

• is_limit (not too long and very clear, that you're at the limit)
• is_past (coincidentally rhymes with is_last for the one-past 😉)
• is_done (works, but then it's counterpart flux::done() counterpart doesn't sound so nice)
• is_stopped (would use pairs flux::start() and flux::stop(), which sounds a bit weird, but not weirder than begin/end)
• is_complete (hmm, maybe)
• is_terminated (bit long)
• is_terminal (maybe)
• is_final (oops, C++ keyword, so can't use that)

And conversely for the counterpart of flux::first(v):

• flux::limit(v) (noun works well here)
• flux::past(v) (clearly evokes the "one past" concept)
• flux::done(v) (😕 hmm, sounds weird because it sounds like a boolean function rather than returning a one-past sentinel marker)
• flux::stop(v) (can be a noun like "gradient stop" or a verb, where verb is weird like "end")
• flux::complete(v) (😕 also sounds like weird like done)
• flux::terminal(v) (but not to be confused with a command line interface 😅)
• flux::final(v) (oops, C++ keyword, so can't use that)

And yes, using any of the above counterparts above would not form a pair like first and last do, but then end-exclusive ranges are already an asymmetric concept [ ).

From your talk, where you say "That's called chain in my library, because that's a better name" and "sum, because that's easier to spell than accumulate", I can see you're not strongly attached to existing names. Do any of the above alternate names convey the concept for you nicely, especially limit or past, because if the 62 upvotes from here mean anything, using last is an non-ideal name? Cheers from Seattle.

Hi Tristan,

Thank you for developing flux... I think functional style C++ is the way to go in a multi-core world and IMHO, the technique has the potential to increase the chances of correct programs.

I was able to build module_test.cpp successfully per your post.

Encouraged, I took the word-count.cpp example and replaced #include <flux> with import flux; and discovered that the build failed due to identifier FLUX_FWD not being defined.

The solution was to copy the macro into word-count.cpp. According to this post, preprocessor macros don't play well with modules so one solution seems to be to create a macro file to be included as well as the import.

FWIW, to my surprise, I found this worked using clang++-17:

namespace flux {
    inline auto forward(auto x) { return static_cast<decltype(x)&&>(x); }
} // flux

I can't tell whether it meets all your requirements, but it would be nice to get rid of as many preprocessor macros as possible!

Marv

If I have a sequence whose element type is T&, are there any rules around what the lifetime of that reference needs to be? Specifically, is this necessary valid:

auto cursor = flux::first(seq);
T& r = flux::read_at(seq, cursor);
flux::inc(seq, cursor);
use(r); // cursor has advanced, can I still use r?

One motivation for this question is how to do algorithms. Like min is currently

where fold_first is

What this means is that if I have a sequence where value=string and element=string const&, and I'm finding the minimum string, the worst-case scenario (the sequence is perfectly sorted, backwards) is that I'm doing N string copies. But in this case, if references were guaranteed/required stable, you could do a much more efficient approach via this:

template <sequence Seq, strict_weak_order_for<Seq> Cmp = std::ranges::less> 
[[nodiscard]] 
constexpr auto min_ref(Seq&& seq, Cmp cmp = Cmp{}) const 
    -> flux::optional<element_t<Seq>> // <== NB
{
    auto cursor = flux::first(seq);
    if (flux::is_last(seq, cursor)) {
        return nullopt;
    }
    
    value_t<Seq> const* best = &flux::read_at(seq, cursor);
    flux::inc(seq, cursor);
    while (not flux::is_last(seq, cursor)) {
        value_t<Seq> const* elem = &flux::read_at(seq, cursor);
        if (std::invoke(cmp, *elem, *best)) {
            best = elem;
        }
        flux::inc(seq, cursor);
    }
    return *best;
}

This does zero string copies. Basically, this is min_element instead of min. This version returns an optional reference, but an equivalent that returns an optional value would still be better since it does exactly 1 string copy.

So I guess the question is:

If a sequence's element type is an lvalue reference, does advancing the cursor invalidate that reference?

If NO, then we probably want a version of fold_first that returns optional<element> instead of optional<value>. Possibly up to even having fold_first itself just only ever return optional<element> (which is what it does in Rust ¹) or possibly have the callable required to either return value or element and return accordingly.

If YES, then... I guess no further work necessary, but probably should be noted somewhere regardless.

I thought I'd open an issue. Per twitter, this test:

doesn't actually test anything about read_only, since flux::ref(arr) is already a read-only sequence, so flux::read_only(flux::ref(arr)) (correctly!) just gives you back flux::ref(arr). You want flux::mut_ref(arr) there.

This also begs the question of to what extend this is a valid implementation of read_only:

 struct read_only_fn {
     template <adaptable_sequence Seq>
     [[nodiscard]]
     constexpr auto operator()(Seq&& seq) const -> read_only_sequence auto
     {
         if constexpr (read_only_sequence<Seq>) {
             return FLUX_FWD(seq);
         } else {
-            return read_only_adaptor<std::decay_t<Seq>>(FLUX_FWD(seq));
+            return flux::map(FLUX_FWD(seq), [](auto&& elem) -> const_element_t<Seq> {
+                return FLUX_FWD(elem);
+            });
         }
     }
 };

It's very nearly correct, the only thing that should break is the contiguous_sequence check in the test. The fact that read_only is a map, just one that's potentially contiguous, feels like it should be implemented like this:

template <class T>
struct cast_to_const {
    template <class U>
    constexpr auto operator()(U&& rhs) const -> T {
        return FLUX_FWD(rhs);
    }
};

template <sequence Base>
    requires (not read_only_sequence<Base>)
struct read_only_adaptor : map_adaptor<Base, cast_to_const<const_element_t<Base>>>
{
    using map = map_adaptor<Base, cast_to_const<const_element_t<Base>>>;

public:
    constexpr read_only_adaptor(decays_to<Base> auto&& base)
        : map(FLUX_FWD(base), cast_to_const<const_element_t<Base>>{})
    {}

    struct flux_sequence_traits : map::flux_sequence_traits {
        static constexpr auto data(auto& self)
            requires contiguous_sequence<Base>
        {
            using P = std::add_pointer_t<std::remove_reference_t<const_element_t<Base>>>;
            return static_cast<P>(flux::data(self.base_)); // error: self.base_ is private
        }
    };
};

But that doesn't quite work. Another approach would be to have flux::read_only just return flux::map using the appopriate cast_to_const and just have map recognize it. That feels a little backwards (why is map adding a function that is only usable for read_only) but avoids all the boilerplate too.

I was wondering if we could have a logo. I have prepared one proposal:

This was one of the very first adaptors and I just adapted my ranges implementation without thinking about it too much. But how can we bounds check if we don't know where the end is?

From @codereport on Twitter "X":

I was looking at that solution the other day and have been meaning to open an issue requesting the equivalent of range-v3's adjacent_remove_if

So here it is!

int main() {
    const std::vector<std::string> vec{"a", "b", "c"};

    auto str = flux::ref(vec).flatten().to<std::string>(); // Error, out-of-bounds access
}

Gives:

/opt/compiler-explorer/libs/flux/trunk/include/flux/core/default_impls.hpp:193: Fatal error: out-of-bounds sequence access
terminate called without an active exception
Program terminated with signal: SIGSEGV

https://flux.godbolt.org/z/Eo3e9vrPM

It looks like Homebrew has updated the version of lcov from 1.16 to 2.0, which has broken things.

An assertion is triggered due to the drop in intersperse.
See https://cpp1.godbolt.org/z/ff99sqcK5:

#include "https://raw.githubusercontent.com/tcbrindle/flux/main/single_include/flux.hpp"

using namespace flux;

auto intersperse(auto&& r, auto&& e) -> auto { return FLUX_FWD(r).map([_0 = e](auto const& x) -> auto { return std::vector{_0, x};  }).flatten().drop(1);  }

auto sfml_argument(std::string_view) -> std::string { return "abc";  }

auto sfml_argument_list(std::span<std::string_view> mf) -> std::string { 
    return "(" + intersperse(drop(mf, 1).map(sfml_argument), std::string(", ")).flatten().to<std::string>() + ")";  }

auto main() -> int{
  std::vector<std::string_view> v {"point"}; 
  (void)sfml_argument_list(v);
}

/app/raw.githubusercontent.com/tcbrindle/flux/main/single_include/flux.hpp:1136: Fatal error: assertion 'self.has_value()' failed
terminate called without an active exception
Program terminated with signal: SIGSEGV

The same happens here (https://cpp1.godbolt.org/z/s4xGzzK3j):

#include "https://raw.githubusercontent.com/tcbrindle/flux/main/single_include/flux.hpp"

#include <array>
#include <iostream>
#include <iterator>

int main()
{
    auto result = flux::from(std::array{1, 2})
                                .filter(flux::pred::even)
                                .drop(2)
                                .drop(1);
    result.output_to(std::ostream_iterator<int>{std::cout});
}

When using the Visual Studio generator to build flux I'm now getting this build error:

flux\test\test_read_only.cpp(132,28): error C2607: static assertion failed
flux\test\test_read_only.cpp(132,28): message : the concept 'std::same_as<std::pair<const int &,const double &>,std::pair<const int &&,const double &&>>' evaluated to false
C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Tools\MSVC\14.37.32822\include\concepts(36,9): message : 'std::pair<const int &,const double &>' and 'std::pair<const int &&,const double &&>' are different types

The offending code in concepts.hpp. FLUX_HAVE_CPP23_TUPLE_COMMON_REF is true in this context.

#ifdef FLUX_HAVE_CPP23_TUPLE_COMMON_REF
    std::common_reference_with<element_t<Seq>&&, value_t<Seq>&> &&
    std::common_reference_with<rvalue_element_t<Seq>&&, value_t<Seq> const&> &&
#endif

I am trying to use Flux to simplify dot products with circular buffers.
I have an implementation that manually uses STL on two sub-ranges. This is really fast, but you have to do some manual book-keeping and if you care about more than one STL algorithm (inner_product in this case), then you have to reimplement everything yourself on the two sub-ranges.

I want to use Flux to define a sequence adaptor, and since a flux sequence defines iterators, I can in theory use that with std::inner_product to compute my dot products.

However, I'm having trouble adapting the container.
Here is a short link https://godbolt.org/z/3PKeT5Wee that better explains my intention.
Thank you

Hey @tcbrindle,

There is an issue with the flux::scan function. It seems as if you are initializing the state to zero, instead of applying the binary operation to the first two elements. It means anything that doesn't have 0 as the "identity" element will break. https://flux.godbolt.org/z/8YK6aErh5

auto iota_scan(int n, auto f) {
    return flux::iota(1, n + 1).scan(f).template to<std::vector>();
}

int main() {
    fmt::print("{}\n", iota_scan(5, std::plus{}));        // ✅ [1, 3, 6, 10, 15]
    fmt::print("{}\n", iota_scan(5, std::multiplies{}));  // ❌ [0, 0, 0, 0, 0]
    fmt::print("{}\n", iota_scan(5, std::ranges::max));   // ✅ [1, 2, 3, 4, 5]
    fmt::print("{}\n", iota_scan(5, std::ranges::min));   // ❌ [0, 0, 0, 0, 0]
}

Technically the max scan would break as well if you had negative numbers.

I'm trying to implement trim by two drop_while and reverse, but I am getting compilation error.

    std::string s = "   abc     ";
    flux::write_to(flux::from(s).drop_while(isspace)
                                .reverse()
                                .drop_while(isspace)
                                .reverse(), std::cout);

https://godbolt.org/z/TPqT6dec7

We have several adaptors and algorithms which take a comparator, and require that the comparator produces a strict weak order over the sequence elements:

• find_min/find_max/find_minmax
• min/max/minmax
• sort
• set_union/set_difference/set_symmetric_difference/set_intersection
• cmp::min/cmp::max (for a sequence of two elements)

The comparator for all of these functions follows the classic STL model of requiring a binary predicate which returns true if the first argument is "less than" the second, defaulting to std::ranges::less. We use the standard library std::strict_weak_order concept, in most cases via our own strict_weak_order_for<Seq1, Seq2> concept which checks std::strict_weak_order for all combinations of the sequences' element_t, value_t& and common_element_t (the Flux equivalent of Ranges' std::indirect_strict_weak_order).

The outlier here is flux::compare(seq1, seq2, cmp) which requires the comparator to return a value of one of the three C++20 comparison categories (std::partial_ordering, std::weak_ordering or std::strong_ordering) and performs a lexicographical comparison of the sequence elements returning that category -- that is, the same as std::lexicographical_compare_three_way.

First of all, this is inconsistent. We shouldn't have one algorithm with a completely different interface to all the others.

A simple solution would be to change our compare to be the equivalent of std::lexicographical_compare -- that is, require just a "less than" predicate like everything else.

A potentially better solution would be to consistently use three way comparison everywhere -- specifically, requiring a comparator for all of the above algorithms (except compare) to return at least std::weak_ordering. After all, we're a C++20 library, we can do things the modern way!

As with everything though, there are pros and cons to doing this:

Pros:

• Correctness. At the moment, strict weak ordering is basically just a semantic requirement. Although a user could theoretically supply a custom comparator that returns std::weak_ordering but "lies" about it, this seems much less likely than accidentally passing an incorrect predicate.
• Proper handling of NaNs: Right now, flux::sort(vector<float>) compiles but does the wrong thing if the data contains NaN values. With the proposed change (assuming std::compare_three_way as the default comparator) then this will fail to compile. This forces the user to think about how they want to handle NaNs; either by passing std::strong_order to use the IEEE total ordering, or by using a custom comparator that ignores NaN values.

Cons:

• By default, only types with a spaceship operator could be used with the Flux algorithms. Of course, defaulting the operator is very easy in C++20, but there's probably a lot of code out there that only defines the classic relational operators
• Potentially, worse codegen. These algorithms only really care about less-than, but custom comparators (or op<=> implementations) might need to do two compares rather than one. It's probably worth benchmarking this. In particular, using std::strong_order to compare floats generates a lot more code than std::less.
• Ergonomics: right now it's easy to sort in descending order by saying sort(vec, std::greater{}). We'd probably want to provide a comparator that inverts ordering::greater and ordering::less to allow the same thing without the user needing to write a lambda to do it themselves.
• Unfamiliarity: the STL has used less-than predicate comparators for 30 years, and now suddenly we're asking people to do something different. Likewise, "why can't I use flux::sort on my vector of doubles, std::sort works fine"

Overall, I think this is worth investigating -- at least, benchmarking what happens if we use our current sort with a comparator defined as (roughly):

bool cmp(T& lhs, T& rhs) { return std::is_lt(std::weak_order(lhs, rhs)); }

and seeing what happens.

C++20 provides both std::ranges::min() (an overload of which takes an input range and returns the value of the least element) and std::ranges::min_element() (which takes a forward range and returns an iterator to the least element).

In Flux we currently have flux::min() which is the equivalent of the first function, except that we return an optional to avoid UB in the case where the sequence is empty.

We should also provide an equivalent for min_element(), taking a multipass_sequence and returning a cursor to the least element. Because we use the term "element" in Flux to mean a member of a sequence in general, reusing the standard library function name could be confusing, so instead we'll go for find_min() -- which makes it clear that it's returning a cursor, like the rest of the find() family.

Of course, we should have find_max() and find_minmax() (returning a pair of cursors) too.

Related: #101

https://flux.godbolt.org/z/MhGqKPjnr

#include <flux.hpp>
#include <iostream>

int main(){
    flux::iota(1,4)
        .drop(2)
        .reverse().drop(5).reverse()
        .filter([](int i) { return i&1; })
        .chunk(4)
        .write_to(std::cout);
    // [[2]]
}

@tcbrindle says we should fix that at some point!

I'm currently getting this build errors when trying to build using Ninja and Clang 16.0.6 on Windows.

A brief snippet of the errors I'm getting (currently 309 total). ~200 of the errors are complaining that std::source_location can't be found. <source_location> is clearly included and LLVM on Windows depends on Microsoft's STL, so I'm fairly certain that std::source_location is in fact available.

In file included from D:/Repositories/flux/include\flux/core/utils.hpp:9:
D:\Repositories\flux\include\flux\core\assert.hpp(28,33): error G4D3043E2: no type named 'source_location' in namespace 'std'
                             std::source_location loc = std::source_location::current()) const
                             ~~~~~^
D:\Repositories\flux\include\flux\core\assert.hpp(28,60): error G60A5EC10: no member named 'source_location' in namespace 'std'
                             std::source_location loc = std::source_location::current()) const

Another error I'm getting

GAF447572 no matching function for call to 'inc_ra_impl' D:\Repositories\flux\out\build\x64-debug-clang\flux D:\Repositories\flux\include\flux\op\chain.hpp 230	

If you need more details I can try to dig in a bit deeper and try to understand what is going on.

Given

auto seq = flux::ints(1).take(10).filter(flux::pred::even);

then the internal iteration code path returns five elements as expected:

seq.for_each([](int i) { 
    std::cout << i << ' ';
});
// prints 2 4 6 8 10

However external iteration misses out the last element:

FLUX_FOR(int i, seq) {
    std::cout << i << ' ';
}
// prints 2 4 6 8

https://godbolt.org/z/8ozEsj77d

I recently pulled the latest flux changes and flux no longer builds. I get the following warning.

CMake Error in build/_deps/flux-src/CMakeLists.txt:
  Target "flux" INTERFACE_SOURCES property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the build directory.


CMake Error in build/_deps/flux-src/CMakeLists.txt:
  Target "flux" INTERFACE_SOURCES property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the build directory.Target "flux" INTERFACE_SOURCES
  property contains path:

    "/home/cph/parrot/build/_deps/flux-src/"

  which is prefixed in the source directory.

Maybe I am doing something wrong.

As noted when @isaacy2012 was adding cartesian_power, the current implementation of size() for cartesian_product[_map] uses built-in multiplication in a fold expression, and could easily overflow:

It should use num::checked_mul() instead to guard against UB.

I'm trying zip ints() sequence with the filtered vector, but I am getting compilation error.

std::vector v = {1, 2, 3, 4, 5};
auto res = flux::zip(flux::ints(), flux::from(v).filter(flux::pred::gt(3)));

https://godbolt.org/z/oaEn1vfr7

Given

auto seq = flux::cartesian_product(std::array{1, 2, 3}, flux::empty<int>);

then

assert(seq.is_empty()); // passes 
assert(seq.size() == 0); // passes
assert(seq.is_last(seq.first())); // passes
// But...
assert(seq.first() == seq.last()); // fails!

https://flux.godbolt.org/z/ocMKarfvx

(Note that if the first source sequence of cartesian_product is empty, then all four assertions pass as expected. This only shows up if the first source is non-empty, but one of the other sources is empty.)

The specification for C++23 cartesian_product_view::end() handles this by returning (in Flux terms) tuple{first(base0), first(base1), ...} if any base (from index 1 up) is empty, and tuple{last(base0), first(base1), ...} otherwise. At the moment, we unconditionally return the latter in cartesian_product_adaptor::last(), but we should change this to match the ranges behaviour.

The element type of flux::cartesian_product, cartesian_power and adjacent is a tuple of the element type(s) of the underlying sequences. These three adaptors also provide *_map versions, which take an n-ary function and call it directly with the underlying elements. This is to avoid forming a tuple and then immediately destructuring it, as would happen in a subsequent call to map(unpack(func)).

The odd one out is zip, which doesn't provide a _map form. We should fix that.

Similar to the issue #174, this code also causes clang to crash https://flux.godbolt.org/z/3fT4r548j

We currently have cartestian_product(seq1, seq2, ...) which takes a pack of N sequences and yields N-tuples of all the possible combinations of elements from those sequences. This is equivalent to a set of N nested for loops, and to one form of the Python itertools product operation.

It's pretty common however to want to use the same sequence repeatedly with cartesian_product. Itertools provides a second form of product for this, using a repeat argument. It would be good if we provided an equivalent too.

We'd need it to have a different name, and we'd probably want to take N as a template parameter to avoid having to allocate. So we could have something like products<3>(seq), which would be equivalent to cartestian_product(seq, seq, seq) except that we wouldn't have to store multiple references to/copies of the sequence. The size of the resulting sequence would be size(seq)^N.

Itertools also provides the permutations operation, which would also be nice to have. This yields (in lexicographical order) all the length-N permutations of the elements of the input sequence. This is a strict subset of the elements of products<N>, skipping those tuples which contain repeated elements from the underlying sequence. If S is the size of the original sequence, the size of permutations<N> is S!/(S - N)!.

Finally, Itertools has two slightly different combinations operations. The first gives a strict subset of permutations, skipping tuples in which the elements are not in "sorted" order (according to their position in the initial sequence), and has size S!/N!(S-N)!

The second, the slightly oddly named (to me) combinations.with_replacement. This does the same as combinations except that it additionally allows individual elements to be repeated -- meaning the resulting elements are a subset of product<N>, but not permutations<N>. The number of elements is (S+N-1)!/N!(S-1)!.

To make this a bit more concrete, imagine an input sequenceseq = [a, b, c, d]. Then the various operations give:

products<3>(seq): (4^3 = 64 elements)

aaa, aab, aac, aad, aba, abb, abc, abd, aca, acb, acc, acd, ada, adb, adc, add
baa, bab, bac, bad, bba, bbb, bbc, bbd, bca, bcb, bcc, bcd, bda, bdb, bdc, bdd
caa, cab, cac, cad, cba, cbb, cbc, cbd, cca, ccb, ccc, ccd, cda, cdb, cdc, cdd,
daa, dab, dac, dad, dba, dbb, dbc, dbd, dca, dcb, dcc, dcd, dda, ddb, dcd, ddd   

permutations<3>(seq): (4!/(4-3!) = 24 elements)

abc, abd, acb, acd, adb, adc,
bac, bad, bca, bcd, bda, bdc,
cab, cad, cba, cbd, cda, cdb,
dab, dac, dba, dbc, dca, dcb

combinations<3>(seq): (4!/3!*(4-3)! = 24/6 = 4 elements)

abc, abd, acd, bcd

combinations_with_replacement<3>(seq): ((4+3-1)!/3!(4-1)! = 6!/3!3! = 720/36 = 20 elements)

aaa, aab, aac, aad, abb, abc, abd, acc, acd, add,
bbb, bbc, bbd, bcc, bcd, bdd,
ccc, ccd, cdd,
ddd

Currently internal iteration is achieved by a sequence customisation point for_each_while(predicate) -> cursor_t, which instructs the sequence to iterate over all of its elements until such time as the predicate returns false.

Unfortunately there are some cases where we can't use internal iteration even though we'd like to. Algorithms like fold_first (#98), min and max need to inspect the initial element before iterating over the rest of the sequence; more generally, any time we take a slice of a sequence (such as with the elements of chunk, chunk_by, slide etc) then we can't implement for_each_while() on the slice in terms of an equivalent call on the base sequence, and so have to fall back to external iteration.

A solution to this would be to replace the existing for_each_while() customisation point with a new pair of functions taking extra cursor arguments to indicate where iteration should begin and end:

auto iterate_while(auto& seq, auto&& pred, cursor_t from) -> cursor_t;
auto iterate_while(auto& seq, auto&& pred, cursor_t from, cursor_t to) -> cursor_t;

The slightly odd parameter order is to allow some sequence impls to provide just a single overload, with the to parameter defaulted to flux::last(). Implementations wouldn't need to provide both of these functions: in particular, most single-pass sequences aren't going to be able to provide the second one.

With this approach, algorithms like fold_first could examine the first element before proceeding with a call to iterate_while(); and iterate_while() on slices could be implemented in terms of calls to the equivalent function on their parent sequence. The existing flux::for_each_while(seq, pred) wrapper function could be implemented as a call to iterate_while(seq, pred, first(seq)).

This would add (yet) another customisation point that authors would have to worry about when writing a sequence implementation, which I'm somewhat reluctant to do, but I think the codegen benefits of internal iteration are great enough that it's justified in this case.

@brycelelbach @brevzin @jnytra any thoughts?

Hey! I think, it can be nice to have benchmark results per commit or once-generated at least to understand how it is efficient =)

Currently we optimise output_to() for contiguous_sequences of trivial types to use std::memmove.

There are more places where we could use equivalent low-level optimisations, including

• fill() (using memset())
• equal() (using memcmp())
• compare() (using memcmp())
• find() (using memchr())
• search() (using memmem() where available)

See also the equivalent bug for Nanorange with more information about when these optimisations can be used.

In this issue, I suggest adding set_* sequence adaptors:

• set_union
• set_difference
• set_symmetric_difference
• set_intersection

Hi there
and thanks for you effort to create this nice lib. Are there actually any plans to support "scheduled" operator like debounce, throttle, delay? Or maybe smoothing operators like median or exponential moving average?

Thanks already.

Best regards
Manuel

Replacing some of my ranges filter stuff with flux made it around 25% faster, but I am unable to use flux::proj() for a projection with any():

return ! std::ranges::any_of(mappingsList, [](const auto vk) { return vk == 0; }, &CBActionMap::ButtonVirtualKeycode);
attempt:
return !flux::ref(mappingsList).any([](const auto vk) { return vk == 0; }, flux::proj(std::equal{}, &CBActionMap::ButtonVirtualKeycode));

Documentation doesn't really refer to flux::proj() much at all, beyond a couple instances of it's usage.

Title says it all, exact output is as below:

This is with clang-tidy 16 and 17

/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:92:71: error: Moved-from object 'loc' of type 'std::source_location' is moved [clang-analyzer-cplusplus.Move,-warnings-as-errors]
            assert_fn{}(idx < limit, "out-of-bounds sequence access", std::move(loc));
                                                                      ^
/Users/runner/work/hyperion_assert/hyperion_assert/src/assert/detail/parser.cpp:156:9: note: Loop condition is true.  Entering loop body
        for(auto cur = flux::first(tokens); !flux::is_last(tokens, cur); flux::inc(tokens, cur)) {
        ^
/Users/runner/work/hyperion_assert/hyperion_assert/src/assert/detail/parser.cpp:157:27: note: Calling 'read_at_fn::operator()'
            auto& token = flux::read_at(tokens, cur);
                          ^~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/sequence_access.hpp:42:[16](https://github.com/braxtons12/hyperion_assert/actions/runs/8270441336/job/22627969323#step:7:17): note: Calling 'sequence_traits::read_at'
        return traits_t<Seq>::read_at(seq, cur);
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/default_impls.hpp:193:9: note: Calling 'indexed_bounds_check_fn::operator()'
        indexed_bounds_check(idx, size(self));
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:83:13: note: Assuming the condition is true
        if (!std::is_constant_evaluated()) {
            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:83:9: note: Taking true branch
        if (!std::is_constant_evaluated()) {
        ^
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:85:43: note: Left side of '&&' is false
            if (__builtin_constant_p(idx) && __builtin_constant_p(limit)) {
                                          ^
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:91:66: note: Object 'loc' of type 'std::source_location' is left in a valid but unspecified state after move
            assert_fn{}(idx >= T{0}, "index cannot be negative", std::move(loc));
                                                                 ^~~~~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:92:25: note: Assuming 'idx' is >= 'limit'
            assert_fn{}(idx < limit, "out-of-bounds sequence access", std::move(loc));
                        ^~~~~~~~~~~
/Users/runner/work/hyperion_assert/hyperion_assert/build/env-cc-release/_deps/flux-src/include/flux/core/assert.hpp:92:71: note: Moved-from object 'loc' of type 'std::source_location' is moved
            assert_fn{}(idx < limit, "out-of-bounds sequence access", std::move(loc));