Porting QLever to Cpp17

There currently is an ongoing project to make QLever compliant with C++-17 (in particular with GCC versions starting at 8.3). This page tracks the progress and substeps of the endeavor.

Replacing <ranges>

• The range-v3 library has been integrated into qlever.
• In the file src/backports/algorithm.h (includable via #include "backports/algorithm.h) we have implemented the namespaces ql::ranges and ql::views. These have to be used instead of std::ranges and std::views.
• ql::views / ql::ranges can be configured at compile time to internally either use C++20 <ranges> or range-v3 (via the CMake option) -DUSE_CPP_17_BACKPORTS=ON/OFF.
• Most of the uses of std::ranges/std::views are already replaced in the current master, only a few remaining (see this PR.
• There is a CI check on GitHub actions that automatcially checks that QLever can be compiled with the above cmake options set to ON.

Caveats and oddities when using range-v3

This subsection documents aspects, in which range-v3 is not a simple drop-in replacement for std::ranges as well as the workarounds that currently should be used. The longterm solution would be to patch range-v3, but that is currently out of scope.

• unique has a different interface: range-v3::unique returns an iterator, whereas std::ranges::unique returns a std::ranges::subrange. Current workaround: Simply use std::unique(something.begin(), something.end()).
• <range-v3> uses a strongly typed signed integer as the difference_type of the implemented ranges, which cannot be directly converted to unsigned integers. This currently prevents the rewrite of the two std::views::iota in test/ThreadSafeQueueTest.cpp. The short-term workaround here is to explicitly setup a std::vector instead of the views::iota (it is only a test context, the memory overhead is negligible).

Deliverables for the next step

• Write a small standalone test program that uses the range-v3 library and verify that (in C++-17-mode) this library in principle works on GCC 8.3.
• Replace the remaining occurences of range algorithms and views (all functions and types in the namespace std::ranges/std::views.)
• Do not replace the usage of range concepts (std::ranges::range, std::ranges::forward_ranges etc.), because they additionally require the rewriting of the surrounding concept techniques.

Backporting other standard library functions and types

There are some small and not so small functions and types that are new to C++20 and currently used in QLever, those can (and have to) be reimplemented in C++17. A (currently still incomplete list) follows:

• functions : std::shift_left, std::shift_right , std::erase(_if), std::bit_cast, std::addressof, ...
• types and classes: std::span.

Notes:

• Most elements of the above lists can be implemented with limited effort, with the following caveats:
• The low-level utils like bit_cast and addressof can be implemented in C++17 (see the "possible implementation section" on cppreference, but they can't be constexpr. We have to figure out, whether this is a problem with its current usages in QLever.
• For std::span QLever currently only uses the case of a dynamic extent, and not the full interface. Here we can start with a simple implementation that just stores two pointers begin() and end() and then has the required interface.

Implementation guidelines:

• The replacements should be implemented in the ql::namespace and in header files in the src/backports folder in headers with the same name as the corresponding C++ header. For example, std::span is in the <span> header, so ql::span should be implemented in src/backports/span.h.
• I suggest starting with std::span (some typing, but conceptually simple) and std::erase/std::erase_if (rather simple, no implications).

Backporting Concepts

• C++20 introduces concepts and constraints that are a superior replacement of older SFINAE techniques such as std::enable_if and std::void_t.
• The range-v3 library (included in QLever) as well as QLever itself provide a set of MACROS that expand to concepts in C++20-mode and to std::enable_if in C++17-mode.
• These macros can all be included via #include "backports/concepts.h.

Explanation and examples for the backporting macros.

All of the backport macros are already used in QLever, so you can also grep the codebase for example usages.

• CPP_template (define a template declaration with constraints on the type)

// C++20, variant a
template <std::integral T, std::floating_point F>  // `std::integral` and `std::floating_point` are concepts.
class C{};
// C++20, variant b
template <typename T, typename F> requires (std::integral<T> && std::floating_point<F>)
class D{};
// The corresponding rewrite using `CPP_template`. Note the usage of `CPP_and`.
CPP_template(typename T, typename F)(requires std::integral<T> CPP_and std::floating_point<F>)
class E{};

• CPP_and -> See above, used to rewrite an conjunction && inside constraints.
• CPP_concept define a concept

// Rewrite as follows:
template <typename T>
CPP_concept small = sizeof(T) < 3;
// This is equivalent in C++20 mode to
template <typename T>
concept small = sizeof(T) < 3;
// And in C++17 mode to
template <typename T>
static constexpr bool small = sizeof(T) < 3;

// NOTE: As soon as you rewrite one of the concepts using `CPP_concept` , 
// then you can't use it in `variant A` of the `CPP_template` example 
// above anymore, but have to rewrite the template.

• CPP_ret (used to rewrite return types of auto functions), See the usage in src/engine/sparqlExpressions/LiteralExpression.h, there shouldn't be too much use for it.

• CPP_concept_ref etc. (used to define concepts that use requires clauses like requires(T t) { t.begin(); } has yet to be documented.

• QL_CONCEPT_OR_NOTHING, QL_CONCEPT_OR_TYPENAME, completely documented in src/backports/concepts.h, see there.

Notes and caveats

• We currently do not yet have macros to deal with templates that are declared and defined in separate places (For concepts, the constraint has to be in both places, for enable_if only in the declaration). Currently work with QL_CONCEPT_OR_TYPENAME for these cases where possible, or collect the places where this is necessary, such that we can decide on how to move forward there.

First steps and implementation guides

• There are quite some custom concepts in the util/TypeTraits.h file. For each of them, make it a CPP_concept and rewrite all its usages to CPP_template such that the GitHub actions check with -DUSE_CPP_17_BACKPORTS=ON works.
• Rewrite the places where concepts from std::ranges are used (e.g. std::ranges::range or std::ranges::forward_range) using CPP_template, then the std::ranges can be replaced by ql::ranges.