subrange alternative since views are banned

[Erik Jensen]

If I have an iterator and a sentinel that I want to pass where a range is expected, it appears the C++20 approach is to wrap them in a std::ranges::subrange. However, subrange is currently banned as part of the ban on views, range factories, and range adapters.

I know that for contiguous ranges, I can just use base::span, but is there an equivalent that can be used for non-contiguous ranges?

Alternatively, is there any reason std::ranges::subrange couldn't be allowed by itself? The style guide says that views, range factories, and range adapters are “banned in Chrome due to questions about the design, impact on build time, and runtime performance.” However, subrange by itself seems pretty innocuous. It contains only a start iterator, an end sentinel, and optionally a size, and provides the expected range operations. It seems analogous to both base::span and std::string_view.

[Peter Kasting]

We had some brief discussion about subrange, but I don't know that we considered it deeply, because non-contiguous ranges aren't common. Maybe say more about your use case so we can think about whether there's any alternative already? 

PK

--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/96ca50da-2918-4e32-9df9-0493b63383edn%40chromium.org.

[Erik Jensen]

In my current case, I have a couple of static methods provided for various types via specializations of a class template. I currently have one such specialization/implementation for std::ranges::range. I would like to call one of those methods given two iterators to a std::map forming a range. I could theoretically create my own type that holds the two iterators, implement a specialization for that type, and have the std::ranges::range specialization delegate to it. (e.g., return MyMethod(MyIteratorRange(range.begin(), range.end())) or some such). However, it would be much nicer if I could just wrap the two pointers in a subrange (or equivalent construct) to pass to my existing specialization directly.

[Peter Kasting]

Ok, but what is the method actually doing? Is there a cl you can point at? 

PK

[Erik Jensen]

I don't have a CL to point to, yet. The method is converting the passed data to a GVariant, automatically determining the type of the resulting GVariant based on the type of the data passed. In a GVariant, a dict entry is just a pair of values, and a dictionary is just an array of dict entries, which is why it is reasonable to pass a subrange of a std::map.

Probably also worth noting that this is for work I'm doing in Chrome Remote Desktop, not part of the browser.

[danakj]

Some notes

1. It's important for us to be able to represent a range of a non-contiguous container.

2. Constructing a range from an iterator pair is unsafe and we should avoid doing it that way. If we had this primitive in base that ctor would be marked UNSAFE_BUFFER_USAGE, and we'd want to avoid using it anyway. Instead we'd want to construct a view of the whole map and then narrow it down, that way we get bounds checking and don't get mismatched iterator bugs.

3. We've discussed (in spanification team) about brining an AnySpan-like type that is a view of a container with random-access iterators, and that allows type conversions from the container to the view (such as to make a view of string_views from an array of strings).

4. We haven't had any concrete discussions around providing view types for other containers of non-random-access iterators.

5. I think we do want something here, even a view type with a full set of functionality (map, filter, count, fold, etc...) but not sure about subrange on its own.

6. The advantage of a primitive to combine iterator pairs or iterator/sentinel into a range in the meantime is that you can share range-based code with spans or full containers as well. Not sure if this particular case is using that benefit.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAN%3DK5G_A%2BpX6dVEYw0mM-o8DL1t0ZTWWhm%3DDWMRxk42QnVMZcA%40mail.gmail.com.

[Erik Jensen]

Instead we'd want to construct a view of the whole map and then narrow it down, that way we get bounds checking and don't get mismatched iterator bugs.

I believe that should work fine for my use case.

[Peter Kasting]

TLDR: I am weakly for allowing subrange for now, since I think it is incrementally better than not having it, will not complicate future improvements, and the shape and availability of those future improvements is unclear to me.

Further comments below.

On Friday, July 26, 2024 at 7:29:22 AM UTC-7 danakj wrote:

2. Constructing a range from an iterator pair is unsafe and we should avoid doing it that way. If we had this primitive in base that ctor would be marked UNSAFE_BUFFER_USAGE, and we'd want to avoid using it anyway. Instead we'd want to construct a view of the whole map and then narrow it down, that way we get bounds checking and don't get mismatched iterator bugs.

While I agree that narrowing views (a la subspan) is better where possible, asking callers to do this exclusively is a bridge too far IMO.

Notably, most of the STL algorithms, including the versions in std::ranges::, return iterators. Using things like upper_bound(), equal_range(), or even a simple find() will result in elements or subsequences whose positions are notated by iterators. Until we have a shipping replacement for the STL that returns range-like types for such cases (or requires callers to compose in such a way that it can return such a thing), I think allowing subrange would give callers an easy-to-use way to clearly express intent, which could be migrated to a more bulletproof solution later.

 

3. We've discussed (in spanification team) about brining an AnySpan-like type that is a view of a container with random-access iterators, and that allows type conversions from the container to the view (such as to make a view of string_views from an array of strings).

There's something of a slippery slope here towards a transform view, and the design for such a type ("span, but whose output elements might be changed from the inputs") might not be the same as the design for this case ("span, but whose input elements might not be contiguous"). I'm not opposed in principle to solving either or both cases, just noting that we should be clear about which ones we're solving.

5. I think we do want something here, even a view type with a full set of functionality (map, filter, count, fold, etc...) but not sure about subrange on its own.

I would be opposed to providing rich functionality (map, filter, count) on a view type if we aren't wholesale replacing at least <algorithm> (if not the whole STL), as I think it complicates the picture for users. Ideally, there should be a single best way to express most common intents, and either other routes should be unavailable or it should be obvious when to use them and why.

PK

[Peter Kasting]

Bumping this thread.

Dana filed https://github.com/llvm/llvm-project/issues/107904 about some of the related issues here. For the immediate future, her comment on Slack #cxx was that she was OK using subrange() for now.

I think we should allow subrange. Thoughts?

PK