[ENH] Check validity of coiteration

[adam2392]

Follow-up to #25

Closes: #25 as completed

[hameerabbasi]

You'll need to cherry pick the last few commits/rebase on main.

[adam2392]

I validated that the current checks do what they should be doing. However, I'm having a hard time getting them to be correctly evaluated during compile-time and get the error:

 static_assert expression is not an integral constant expression

However, the function all_ordered_or_have_locate actually returns 1 for example during runtime of the conjunctive merge coiteration test.

[hameerabbasi]

I validated that the current checks do what they should be doing. However, I'm having a hard time getting them to be correctly evaluated during compile-time and get the error:

 static_assert expression is not an integral constant expression

However, the function all_ordered_or_have_locate actually returns 1 for example during runtime of the conjunctive merge coiteration test.

Try making the function F constexpr (a template argument) and passing it into the all_ordered_or_have_locate. Also avoid using any members; just pass in arguments wherever possible.

[adam2392]

Okay so logging some notes here to think out loud what the best solution is...

I would like to recurse over the levels and do something like the following:

// the template parameter I tells us which level we are on
template<class F, class... Levels, std::size_t I>
check_coiterate()
{
    if constexpr (std::get<I>(Levels)::LevelProperties::is_ordered)
    {
           static_assert(std::invoke(F, some_fold_expression<(std::size_of(Levels), I>(false)) == false);
    }
    else
    {
           static_assert(std::invoke(F, some_fold_expression<std::size_of(Levels), I>(false)) == false);
           static_assert(std::invoke(F, some_fold_expression<std::size_of(Levels), I>(true)) == false);
    }
}

where some_fold_expression basically constructs a tuple of booleans that are passed as arguments to F. It constructs a tuple of booleans using the pseudocode below, where for every level before the current index I, it adds false to args and then adds the boolean corresponding to the current index I, and then adds false to args for each level and index after I until it constructs the tuple args that has length LevelsSize.

template <std::size_t LevelsSize, std::size_t I>
constexpr auto some_fold_expression(bool level_bool)
{
     args = [false for _ in range(I)] + [level_bool] + [false for _ in range(LevelsSize - I)];
     return args;
}

[adam2392]

Re the recursion check:

F{}(f_args);

I'm having a hard time figuring out how to invoke the template function F during compile time. I'm on a rabbit hole, but found this which seems to work: https://godbolt.org/z/nd7Ghdqqz. It seems like in C++17 and before, you cannot use a lambda expression as a non-type template parameter(?)

The link I posted shows a possible solution to letting the implementation work as is. However, it requires defining the function slightly differently. Do we care how the function is defined? It's just in unit-tests rn. Is it cuz lambda functions are not constexpr?

WDYT @hameerabbasi can I change the way the functions are constructed in the unit-tests to make this all work, or did you have another idea in mind.

[adam2392]

@hameerabbasi https://godbolt.org/z/arPr3G9x5 shows that we cannot use the lambda function directly in this pattern. Instead, one needs to wrap it into a wrapper class

I guess we haven't really discussed how the F gets constructed/instantiated in the whole code-generation algo, so we could refactor this design?

1. Would the way we define the boolean F function as what you showed today be okay (e.g. a function takes in a parameter pack of booleans)?
2. or should we keep the boolean function F pattern as taking in a tuple of booleans? I tried refactoring the design into this: https://godbolt.org/z/zY8dxEKa6, but I don't think works out correctly because the static_assert is not giving the correct value. My suspicion is that the tuple is not being passed correctly.

[adam2392]

[Update 07/24/23] https://godbolt.org/z/77Kxb63q5 gets it closer, but the issue now remains of how to get the function to be called with a tuple of booleans rather than a parameter pack of booleans: https://github.com/hameerabbasi/xsparse/pull/26/commits/abcd5d9b6bfb4873be508d27e5d1447fdc2483fc. Once we figure this out, then the code should work. The only compiler-errors I get now are related to the compareHelper returning a tuple of booleans, rather than a boolean parameter pack.

In file included from /Users/adam2392/Documents/xsparse/test/source/coiteration_test.cpp:17:
/Users/adam2392/Documents/xsparse/include/xsparse/level_capabilities/co_iteration.hpp:433:31: error: value of type 'std::tuple<bool, bool>' (aka 'tuple<bool, bool>') is not implicitly convertible to 'bool'
                    return !F<compareHelper(iterators, other.iterators)>::value;
                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/adam2392/Documents/xsparse/test/source/coiteration_test.cpp:47:36: note: in instantiation of member function 'xsparse::level_capabilities::Coiterate<xsparse::util::LambdaWrapper<const (lambda at /Users/adam2392/Documents/xsparse/test/source/coiteration_test.cpp:30:25)>::apply, unsigned long, unsigned long, std::tuple<xsparse::levels::dense<std::tuple<>, unsigned long, unsigned long>, xsparse::levels::dense<std::tuple<>, unsigned long, unsigned long>>, std::tuple<>>::coiteration_helper::iterator::operator!=' requested here
    for (auto const [ik, pk_tuple] : coiter.coiter_helper(std::make_tuple(), ZERO))
                                   ^
In file included from /Users/adam2392/Documents/xsparse/test/source/coiteration_test.cpp:17:
/Users/adam2392/Documents/xsparse/include/xsparse/level_capabilities/co_iteration.hpp:433:31: error: value of type 'std::tuple<bool, bool, bool>' (aka 'tuple<bool, bool, bool>') is not implicitly convertible to 'bool'
                    return !F<compareHelper(iterators, other.iterators)>::value;
                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

@hameerabbasi and @bharath2438 wdyt?

[hameerabbasi]

I think the term "tuple unpacking" should get you closer. 😉

[adam2392]

I think the term "tuple unpacking" should get you closer. 😉

I tried:

// a tuple of booleans
const auto result_bools = compareHelper(iterators, other.iterators);

// TODO: I want to unpack the `result_bools` tuple into a variadic template
// which is passed into the function object `F` to check if the coiteration
// is valid.
// A pseudocode example is: `!F<result_bools...>::value`
// Using std::apply to unpack and pass the tuple elements as template arguments
bool result = std::apply([](auto&... args)-> bool {
    !F<decltype(args)...>::value;
}, result_bools);
return result;

But this isn't valid:

In file included from /Users/adam2392/Documents/xsparse/test/source/coiteration_test.cpp:17:
/Users/adam2392/Documents/xsparse/include/xsparse/level_capabilities/co_iteration.hpp:462:28: error: template argument for non-type template parameter must be an expression
                        !F<decltype(args)...>::value;
                           ^~~~~~~~~~~~~~~~~
/Users/adam2392/Documents/xsparse/include/xsparse/level_capabilities/co_iteration.hpp:116:31: note: template parameter is declared here
    template <template<bool...> class F, class IK, class PK, class... Levels, class... Is>
                              ^
1 error generated.
make[2]: *** [CMakeFiles/XSparseTests.dir/source/coiteration_test.cpp.o] Error 1
make[1]: *** [CMakeFiles/XSparseTests.dir/all] Error 2
make: *** [all] Error 2

gonna see if there's anything else to try...

Questions:

1. Isn't the operator!= a runtime function? So how can we pass things via template when they are not known as compile-time?

[adam2392]

I cannot figure out a way to make it work beyond this hack in https://github.com/hameerabbasi/xsparse/pull/26/commits/d5c31caa4eaefc6f15b3d40c3b01b7a5891dd855.

IIUC, leveraging template argument F for something that needs to be computed during runtime in operator!= is not trivial. WDYT @hameerabbasi

Is this solution acceptable?

[adam2392]

Okay @hameerabbasi and @bharath2438 this is good to merge if it looks good to you both

[hameerabbasi]

Thanks a bunch, @adam2392.