Change concept range requirements from Boost.Range to range-expression

[tinko92]

In the discussion for #1129 I noticed reverts for range-based for loops and std::begin, std::end. I understand that those are not strictly guaranteed to work under the concept requirements of Boost.Geometry (requiring applicable geometries to model Boost.Range Random Access Ranges), since a geometry could be implemented as a range in a way that is compatible with Boost.Range but not with the standard's notion of ranges.

Since version 1.75, BG requires compilation with C++11 and C++14 support which brings language and standard library facilities that are similar to what Boost.Range provides and more convenient in some cases. Range functionalities have been further formalized and extended since. I propose changing the BG concept requirements that require Boost.Range Random Access Ranges to instead require ranges that conform to the standards notion of range-expressions (https://eel.is/c++draft/stmt.ranged#1.3), i.e. (IIUC) it is an array or it has t.begin() and t.end() members or begin(t) and end(t) can be found via ADL and those return random access iterators. (There's also the more formal std::ranges::range concept but that was only introduced C++20, although compilation support would not be required to refer to it in documentation.)

Rationale:

• could allow dropping the Boost.Range dependency in favor of using standard library alternatives.
• could allow range-based for-loops over geometries, which, aside from terse notation, document in source code that the loop is iterating over the geometry in the obvious way (no non-obvious iterator manipulation must be expected in the loop body)
• could allow leveraging range-functionality and concepts from C++20 and upward, when the language standard requirement is bumped in the future.

Problems:

• would require code changes from users who use custom geometries that adapt to the range requirement by using custom range types that do not have t.begin()/t.end() members or free functions named begin(t), end(t) that can be found via ADL.

[barendgehrels]

I like your proposal and I would like to move towards that direction.
Because of the problem, we should set a deprecation period and, if possible, create a compiler warning for it like we did for rescaling. At this moment I don't know how that exactly would look like but it can maybe be figured out. Otherwise it should be made clear in the documentation.

[awulkiew]

The problem with this proposal is that Boost.Geometry supports iterators returning non-true/proxy references. Boost.Iterator concepts are used for that where std iterator category is replaced with boost traversal and access categories. This plays well with Boost.Range since e.g. random access range is defined in terms of iterator traversal category. This is not the case for standard ranges. Technically an iterator returning non-true/proxy reference even if its traversal category is random access is legacy input iterator because legacy forward iterator and upwards is required to return true reference. So technically AFAIU we'd have to require C++20 to be sure that the standard supports iterators/ranges that we allow.

That said, AFAIU std::begin/end simply returns iterators whatever they are and it's up to the caller what they're used for. So maybe this would be doable.

I'd also think about dropping Boost.Iterator dependency but I don't know how trivial that would be because as I said above an iterator could have random access traversal category, readable access category and std input iterator category at the same time.

[tinko92]

Thank you for the detailed feedback. When you say

technically AFAIU we'd have to require C++20

do you refer to concept checking because C++20 brings the new random_access_iterator concept or to the use of standard algorithms? E.g., is this

geometry/include/boost/geometry/algorithms/detail/buffer/piece_border.hpp

Line 68 in ee83f57

lower = std::lower_bound(begin, end, value, compare);

technically a problem because the iterator should be LegacyForwardIterator?

Edit: picked another example.

[awulkiew]

In C++20 iterator concepts are defined differently and AFAIU it's enough for RandomAccessIterator to be IndirectlyReadable like InputIterator.

Yes, in practice the problem I'm pointing out could arise when legacy iterators are used in standard-conformant way, e.g. in standard algorithms but in Boost as well. In addition to this AFAIR Boost.Iterator can perform standard-conformant translation from boost traversal and access categories to standard iterator category also based on type returned from operator* so what we consider to be random access may be translated to input iterator.

As for the standard algorithms not only the complexity could be different than expected but also some of them could not compile because they might require e.g. LegacyForwardIterator like std::fill or std::search.

On the other hand if we adapted some iterator to the legacy standard concept incorrectly and even though proxy reference was returned adapted it as LegacyRandomAccessIterator then some algorithm could assume that reference returned by operator* is a real one and the result would be dangling reference which would be far worse.

[awulkiew]

Furthermore if we decided to stop using Boost.Range directly we wouldn't be able to drop this dependency because other libraries that we use depend on it, i.e. Algorithm, LexicalCast and by extension Math and Multiprecision. If we add Iterator into the mix then by extension Tokenizer.