# Type erasure for forwarding ranges in combination with "subrange-y" view adaptors

| Key               | Value                                             |
|-------------------|---------------------------------------------------|
| Document Number:  | P1739                                             |
| Date:             | 2019-06-12                                        |
| Reply-To:         | Hannes Hauswedell (h2 AT fsfe.org)                |
| Audience:         | LEWG                                              |

## 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. `view::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".

## Motivation and Scope

Given the following example:

```cpp
vector vec{1, 2, 3, 4, 5};
span s{vec.data(), 5};
auto v = s | view::drop(1) | view::take(10)
           | view::drop(1) | view::take(10);
```

The type of `v` will be something similar to
```
ranges::take_view<ranges::drop_view<ranges::take_view<ranges::drop_view<span<int, dynamic_extent> > > > >
```

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 | view::drop(1) | view::take(3)` should be equivalent to `s.subspan(1, 3)` if `s` is a `span`.

We propose that `view::drop` and `view::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 a `ranges::subrange` over its own (adjusted) iterator and sentinel. This includes:
  * a `span` of dynamic extent;
  * a `basic_string_view`;
  * a `ranges::subrange` that models `ranges::RandomAccessRange` and `ranges::SizedRange`

We also propose that the `view::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 `view::drop` and `view::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.

## Impact on the Standard

This proposal includes changes to

  * the current draft standard
  * [P1035](https://wg21.link/p1035) (most of it currently @ LWG)

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 depends on the following proposals:

  * [P1391](https://wg21.link/p1391) Range constructor for `std::string_view`
  * [P1394](https://wg21.link/p1394) Range constructor for `std::span`

## Design Decisions

### Possible objections to this proposal

Following this proposal means that it will not hold any longer that *"the expression `view::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](https://wg21.link/P1252) modified `view::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.

### Stronger proposals

This proposal originally included also changing `view::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`.
`view::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 `view::all` in this manner would have a much stronger type-erasing effect, e.g. `s | view::drop(1) | view::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 modeled by an input type erased in the above fashion.
For this reason Casey Carter argued against changing `view::all` and it was dropped from this proposal.

[The type erasure proposed for `view::take` and `view::drop` does not suffer from this uncertainty, because we are preserving the exact input type.]

## Technical Specifications

Changes to `view::counted` (24.7.9):

```diff
 The name view::counted denotes a customization point object. Let E and F be expressions, and let T be decay_­t<decltype((E))>. Then the expression view::counted(E, F) is expression-equivalent to:
  - If T models Iterator and decltype((F)) models ConvertibleTo<iter_­difference_­t<T>>,
+   - span{addressof(*E), static_­cast<iter_­difference_­t<T>>(F)} if T models ContiguousIterator.
    - subrange{E, E + static_­cast<iter_­difference_­t<T>>(F)} if T models RandomAccessIterator.
    - Otherwise, subrange{counted_­iterator{E, F}, default_­sentinel}.
  - Otherwise, view::counted(E, F) is ill-formed. [ Note: This case can result in substitution failure when view::counted(E, F) appears in the immediate context of a template instantiation. — end note]
```

Changes to `view::take` (24.7.6.4):

```diff
 The name view::take denotes a range adaptor object.
- For some subexpressions E and F, the expression view::take(E, F) is expression-equivalent to take_­view{E, F}.
+ Let E and F be expressions, and let T be remove_cvref_t<decltype((E))>.
+ Then the expression view::take(E, F) is expression-equivalent to:
+ - T{ranges::subrange{ranges::begin(E), ranges::begin(E) + min<iter_­difference_­t<iterator_t<decltype((E))>>>(ranges::size(E), F)}} if that is well-formed and T models forwarding-range.
+ - ranges::take_­view{E, F} if that is well-formed.
+ - Otherwise view::take(E, F) is ill-formed.
```

Changes to `view::drop` (§4 of [P1035](https://wg21.link/p1035))

```diff
 The name view::drop denotes a range adaptor object.
- For some subexpressions E and F, the expression view::drop(E, F) is expression-equivalent to drop_­view{E, F}.
+ Let E and F be expressions, and let T be remove_cvref_t<decltype((E))>.
+ Then, the expression view::drop(E, F) is expression-equivalent to:
+ - T{ranges::subrange{ranges::begin(E) + min<iter_­difference_­t<iterator_t<decltype((E))>>>(ranges::size(E), F), ranges::end(E)}} if that is well-formed and T models forwarding-range.
+ - ranges::drop_­view{E, F} if that is well-formed.
+ - Otherwise view::drop(E, F) is ill-formed.
```

These wording changes depend on [P1391](https://wg21.link/p1391) & [P1394](https://wg21.link/p1394) which elegantly unify the interfaces of all affected types. Our changes could be adapted to work without, but it would be a lot less pretty.

## Acknowledgements

Thanks to Casey Carter, Eric Niebler, Barry Revzin and Corentin Jabot for feedback on the proposal.

## References

  * [P1252](https://wg21.link/P1252) Input range adaptors
  * [P1035](https://wg21.link/p1035) Ranges Design Cleanup
  * [P1391](https://wg21.link/p1391) Range constructor for `std::string_view`
  * [P1394](https://wg21.link/p1394) Range constructor for `std::span`