Re: [PATCH 2/2] libstdc++: P1739R4 Avoid template bloat for safe_ranges in combination with ...

[Jonathan Wakely <jwakely@redhat.com>]

On 19/02/20 23:53 -0500, Patrick Palka wrote:
>... 'subrange-y' view adaptors
>
>This implements an interpretation of P1739R4.  It's only an "interpretation"
>becuase AFAICT there is an issue with the paper's wording as-is.  So this patch
>deviates from paper when it comes to the problematic wording.
>
>The issue is that the paper's wording for views::take requires that the
>views::take of a specialization of subrange is not just another subrange, but
>specifically is the same specialization as the input subrange.
>But if, say, the input subrange does not model common_range, then the expression
>in section 6.1
>
>    T{begin(E), begin(E) + min(size(E), F)}
>
>is ill-formed because T -- a specialization of subrange which does not model
>common_range -- must be constructed with an iterator-sentinel pair and not an
>iterator-iterator pair.  A similar issue arises with the views::take of an
>iota_view whose value type differs from the type of its bound.
>
>So in light of this issue, this patch deviates from the paper's wording here by
>allowing the views::take of a subrange/iota_view input to be a different
>specialization than that of the input.
>
>Moreover, I found myself needing to define an extra constrained constructor
>iota_view(iterator_, iterator_) alongside the newly added
>iota_view(iterator_, sentinel_) constructor, so that the expression
>in views::take
>
>    iota_view<ValueType,ValueType>{begin(E), begin(E) + min(size(E), F)}
>
>is well-formed in general.  Despite these deviations, the intended end result
>remains the same AFAICT.

Please be sure to report these to the LWG chair address so issues can
be opened.

>@@ -1965,10 +1993,70 @@ namespace views
>
>   namespace views
>   {
>+    namespace __detail
>+    {
>+      template<typename _Tp>
>+	inline constexpr bool __is_empty_view = false;
>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_dynamic_span = false;
>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_dynamic_span<span<_Tp, dynamic_extent>>
>+	  = true;
>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_basic_string_view = false;
>+
>+      template<typename _CharT, typename _Traits>
>+	inline constexpr bool
>+	  __is_basic_string_view<basic_string_view<_CharT, _Traits>> = true;

I think it should be possible to define these without including <span>
and <string_view>. Either by adding forward declarations of span and
basic_string_view, which is sufficient to define the variable template
specializations, or by defining something here and specializing it in
<span> and <string_view> e.g. in <ranges>:

   template<typename _Tp>
     inline constexpr bool __is_viewish = false;

And then in <span> add:

   template<typename _Tp>
     extern inline const bool __is_viewish;
   template<typename _Tp>
     inline constexpr bool __is_viewish<span<_Tp>> = true;

The first declaration is needed so that <span> works without including
<ranges>, and vice versa.

And in <string_view>:

#if __cplusplus > 201703L
   template<typename _Tp>
     extern inline const bool __is_viewish;
   template<typename _Ch, typename _Tr>
     inline constexpr bool __is_viewish<basic_string_view<_Ch, _Tr>>
       = true;
#endif

That way we don't need to declare span and string_view in <ranges> at
all. We also don't need two separate variables, one will do. And
finally, doing it this way allows us to enable this feature for
experimental::basic_string_view too:

And in <experimental/string_view>:

#if __cplusplus > 201703L
   template<typename _Tp>
     extern inline const bool __is_viewish;
   template<typename _Ch, typename _Tr>
     inline constexpr bool
       __is_viewish<experimental::basic_string_view<_Ch, _Tr>> = true;
#endif

This last specialization *must* be defined in
<experimental/string_view> not in <ranges>, because we don't want to
"leak" the non-reserved "experimental" name into <ranges> when the
user hasn't explicitly included a TS header.

A better name than "viewish" would be nice, but it does look like we
can use the same one for span and string_view, since you always treat
them the same.


>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_iota_view = false;
>+
>+      template<weakly_incrementable _Winc, semiregular _Bound>
>+	inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true;
>+
>+      template<typename _Tp>
>+	inline constexpr bool __is_subrange = false;
>+
>+      template<typename _It, typename _Sent, subrange_kind _Kind>
>+	inline constexpr bool
>+	  __is_subrange<subrange<_It, _Sent, _Kind>> = true;
>+    }
>+
>     inline constexpr __adaptor::_RangeAdaptor take
>-      = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
>+      = [] <viewable_range _Range> (_Range&& __r, range_difference_t<_Range> __n)
>       {
>-	return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
>+	using _Tp = remove_cvref_t<_Range>;
>+	if constexpr (__detail::__is_empty_view<_Tp>)
>+	  return std::forward<_Range>(__r);
>+	else if constexpr (random_access_range<_Tp> && sized_range<_Tp>)
>+	  {
>+	    // XXX: we diverge from P1739R4 here in the way we fold iota_view
>+	    // and subrange.
>+	    auto __begin = ranges::begin(__r);
>+	    auto __size = std::min<decltype(__n)>(ranges::size(__r), __n);
>+	    if constexpr (__detail::__is_dynamic_span<_Tp>
>+			  || __detail::__is_basic_string_view<_Tp>)
>+	      return _Tp{__begin, __begin + __size};
>+	    else if constexpr (__detail::__is_iota_view<_Tp>)
>+	      {
>+		using _ValueType = range_value_t<_Tp>;
>+		return iota_view<_ValueType, _ValueType>{__begin,
>+							 __begin + __size};
>+	      }
>+	    else if constexpr (__detail::__is_subrange<_Tp>)
>+	      return subrange{__begin, __begin + __size};
>+	    else
>+	      return take_view{std::forward<_Range>(__r), __n};
>+	  }
>+	else
>+	  return take_view{std::forward<_Range>(__r), __n};
>       };
>   } // namespace views
>
>@@ -2135,9 +2223,24 @@ namespace views
>   namespace views
>   {
>     inline constexpr __adaptor::_RangeAdaptor drop
>-      = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
>+      = [] <viewable_range _Range> (_Range&& __r, range_difference_t<_Range> __n)
>       {
>-	return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
>+	using _Tp = remove_cvref_t<_Range>;
>+	if constexpr (__detail::__is_empty_view<_Tp>)
>+	  return std::forward<_Range>(__r);
>+	else if constexpr (random_access_range<_Tp> && sized_range<_Tp>
>+			   && (__detail::__is_dynamic_span<_Tp>
>+			       || __detail::__is_basic_string_view<_Tp>
>+			       || __detail::__is_iota_view<_Tp>
>+			       || __detail::__is_subrange<_Tp>))
>+	  {
>+	    auto __begin = ranges::begin(__r);
>+	    auto __size = std::min<decltype(__n)>(ranges::size(__r), __n);
>+	    auto __end = ranges::end(__r);
>+	    return _Tp{__begin + __size, __end};
>+	  }
>+	else
>+	  return drop_view{std::forward<_Range>(__r), __n};
>       };
>   } // namespace views
>
>@@ -2903,7 +3006,9 @@ namespace views
>       constexpr auto
>       operator()(_Iter __i, iter_difference_t<_Iter> __n) const
>       {
>-	if constexpr (random_access_iterator<_Iter>)
>+	if constexpr (contiguous_iterator<_Iter>)
>+	  return span{to_address(std::move(__i)), __n};

Ah, this means we need to include <span> in <ranges> anyway. That's
OK, span isn't the biggest header. I'd still like to avoid including
<string_view> if possible though.