Avoid template bloat for forwarding ranges in combination with ‘subrange-y’ view adaptors.

Document #: P1739R2
Date: 2019-10-06
Project: Programming Language C++
Library Working Group
Reply-to: Hannes Hauswedell
<<h2 AT fsfe.org>>

1 Revision History

1.1 R2

  1. Change the name of the paper to reflect more accurately that no type erasure happens (in contrast to the earliest versions of this parper).
  2. Updated standard references to the CD; track naming changes.
  3. Provide html, because markdown isn’t rendered automatically.

1.2 R1

  1. In the changes for views::take and views::drop, also consider constructors of the input type that take iterator and sentinel as arguments (instead of just a constructor that takes a subrange over the two). This enables us to act on such types that don’t provide the range-constructor (e.g. unclear for basic_string_view, in general single-argument constructors are unpopular…). If both constructors are available we prefer the (iterator, sentinel)-constructor to avoid unnecessarily instantiating the subrange-template.
  2. We have added such an (iterator, sentinel)-constructor to ranges::empty view so that it becomes one of the types that benefit from the changes to views::take and views::drop.

These changes were approved by LEWG as part of the discussion of R0 in Cologne.

1.3 R0

First revision.

2 Introduction

The current draft standard introduces many range adaptor objects [24.7]. Upon invocation, most of these return a type that is specified together with the adaptor, e.g. views::take returns a specialization of ranges::take_view. Chaining multiple adaptors thus leads to an increasingly nested type. This proposal suggests avoiding nested return types when the input is a view that already represents a “subrange” and it suffices to “change the bounds”.

3 Motivation and Scope

Given the following example:

The type of v will be something similar to

Although in fact it could just be span<int, dynamic_extent>, i.e. the same as the original type of s. This is also true for other input types that are “subrange-y” and it would feel natural to preserve the original type if only the size of the “subrange” is changed, i.e. s | views::drop(1) | views::take(3) should be equivalent to s.subspan(1, 3) if s is a span.

We propose that views::drop and views::take return a range of the same type as the input type (and not return a nested type) if the input is a forwarding-range that can be constructed from its own (adjusted) iterator and sentinel (or a ranges::subrange over the iterator-sentinel-pair). This includes:

We also propose that the views::counted range factory return a span of dynamic extent (instead of ranges::subrange) if the iterator passed to it models ContiguousIterator.

The proposed changes will strongly reduce the amount of template instantiation in situations where views::drop and views::take are applied repeatedly. They increase the integration of the view machinery from ranges with the views created in the standard independently (span and basic_string_view). And they improve the teachability and learnability of views in general, because some of the simplest view operations now return simpler types and behave as the already documented member functions.

4 Impact on the Standard

This proposal includes changes to the current draft standard. All proposed changes are library changes and none of the proposed changes affect the published international standard.

The proposal targets C++20, because applying these changes afterwards would be breaking.

The currently proposed wording changes depend on the following proposals:

Although the wording could be adapted to handle the mentioned types specifically – if the respective papers are not accepted (in time).

P1664 defines concepts that this proposal could use to specify its behaviour more elegantly. It generalises the notion of reconstructible-ranges and makes more ranges “reconstructible” that can then benefit from the optimisations/fixes described here.

5 Design Decisions

5.1 Possible objections to this proposal

Following this proposal means that it will not hold any longer that “the expression views::take(E, F) is expression-equivalent to take_­view{E, F}, i.e. the adaptor has behaviour that is distinct from the associated view class template. This may be a source of confusion, however by design of the current view machinery users are expected to interact with “the view” almost exclusively through the adaptor/factory object. And this is not the first proposal to define such specialised behaviour of an adaptor depending on its input: P1252 (accepted) modified views::reverse to “undo” the previous reversal when passed a type that already is a specialisation of ranges::reverse_view (instead of “applying” it a second time). The added flexibility of the adaptor approach should be seen as a feature.

While specialisations of e.g. ranges::take_view provide a base() member function that allows accessing the underlying range, this is not true for span or the other return types that we are proposing. However, since the underlying range is of the same type as the returned range, we see little value in re-transforming the range to its original type. It should also be noted that this “feature” (a base() member function) is provided only by some of the views in the draft standard and is not a part of the general view design. It cannot be relied on in generic contexts and combinations with other views and no parts of the standard currently make use of it.

5.2 Stronger proposals

This proposal originally included also changing views::all to type-erase basic_string constants to basic_string_view; all forwarding, contiguous ranges to span; and all forwarding, sized, random-access ranges to ranges::subrange. views::all is the “entry-point” for all non-views in a series of view operations and normally wraps non-view-ranges in ranges::ref_view. Changing views::all in this manner would have a type-erasing effect, e.g. s | views::drop(1) | views::take(3) would return a span, independent of whether s is a span, a vector or an array.

This form of type erasure would preserve all range concepts currently defined. It is, however, possible that future more refined concepts would no longer be modelled by an input type erased in the above fashion. For this reason Casey Carter argued against changing views::all and it was dropped from this proposal.

[The current proposal does not suffer from this uncertainty, because we are preserving the exact input type and there is no erasure.]

6 Technical Specifications

6.1 Changes to views::counted (§24.7.12):

6.2 Changes to views::take (§24.7.6.4):

These wording changes depend on P1391 & P1394 – however the range constructors are no longer required, because we look for (iterator, sentinel)-constructors, too.

6.3 Changes to views::drop (§24.7.8.3):

These wording changes depend on P1391 & P1394 – however the range constructors are no longer required, because we look for (iterator, sentinel)-constructors, too.

6.4 Changes to empty_view (§24.6.1):

The following changes make ranges::empty_view a type that gets special treatment from views::take and views::drop.

In §24.6.1.2:

And add §24.6.1.3:

7 Acknowledgements

Thanks to Casey Carter, Eric Niebler, Barry Revzin and Corentin Jabot for feedback on the proposal. Many thanks to JeanHeyd Meneide for alerting me to and involving me in P1664 which would solve some of the things described here more elegantly (and more generically).

8 References