ranges algorithms

[Dana Jansens]

Hello,

C++20 approval has excluded "ranges" however I want to break the ranges idea into three separate parts:

1. ranges algorithms, found in the <algorithms> header: https://en.cppreference.com/w/cpp/algorithm/ranges

These algorithms depend on the concept of ranges (which we can loosely think of as containers or views with begin/end method pairs).

These provide strictly better and safer APIs than the traditional iterator-pair algorithms. I am aware of no concerns with using these better algorithms. And I think we should allow them.

We also model some of these in base::ranges, and we should migrate those.

2. ranges overloads, such as a ctor or method that takes a range-concept-matching object (such as a container or view) instead of taking iterator pairs.

Like 1 above, these are strictly better and safer API overloads, and we should encourage their use. These are not part of "the ranges library" and are methods found on other types. So they may not have been excluded but they depend on the concept of ranges, so I think we should explicitly allow them.

3. ranges types, found in <ranges>: https://en.cppreference.com/w/cpp/header/ranges

These are new library types that provide functional/iterator-based programming primitives. There are concerns about correctness (e.g. borrowed_range is wrong for non-std view types), compile times, and legibility (e.g. with the | operator, which suffers similar problems as streams) with these types, and we should not allow them at this time.

Cheers,

Dana

[K. Moon]

I'm not very familiar with ranges, but these arguments SGTM.

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAHtyhaSQx%3DAFWiADNthCjEMuoE5CBpVdwyGdQjCsDQSe-bYnWQ%40mail.gmail.com.

[Peter Kasting]

In general I'm fine with this, but note that the base::ranges algorithms are not always identical to the std:: ones (because the std:: ranges algorithms changed some return types versus non-ranges), and we should (a) make sure none of those changes guide people to using <ranges> types or machinery and (b) have a migration plan (presumably this is easily fixed by hand).

PK

On Mon, Nov 13, 2023, 1:07 PM Dana Jansens <dan...@chromium.org> wrote:

--

[Anton Bikineev]

Allowing range algorithms sounds good to me. They enable better ergonomics, bring some safety advantages (e.g. std::dangling), clearer error messages due to constrained parameters (and can even be more performant with std::unreachable_sentinel). I think the only concern could be compile-time overhead:

 - the niebloid machinery requires more template instantiations than what you get with simple template functions in iterator-based algorithms;

 - you get constraint checking.

However, IMHO, the pros outweigh the cons.

I agree that allowing views could be dangerous, especially because of the caching semantics in the filtering views (breaks const iteratability and is not thread-safe).

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFAOQ9OGoXE9KeK7T-KYEkdj6Lut33UtGEuqGUkYisamhg%40mail.gmail.com.

[Kyle Charbonneau]

1 + 3 sgtm.

 

2. ranges overloads, such as a ctor or method that takes a range-concept-matching object (such as a container or view) instead of taking iterator pairs.

Just to clarify, do you mean range overloads provided from allowed STL types/functions or user implemented range overloads? 

Does the STL make use of ranges anywhere outside of <range> and range based algorithms in C++20? I see that C++23 adds range based constructors/methods to STL container types but I don't see anything like that in C++20.

--

[Dana Jansens]

On Tue, Nov 14, 2023 at 9:26 AM Kyle Charbonneau <kyle...@chromium.org> wrote:

1 + 3 sgtm.

 

2. ranges overloads, such as a ctor or method that takes a range-concept-matching object (such as a container or view) instead of taking iterator pairs.

Just to clarify, do you mean range overloads provided from allowed STL types/functions or user implemented range overloads? 

Does the STL make use of ranges anywhere outside of <range> and range based algorithms in C++20? I see that C++23 adds range based constructors/methods to STL container types but I don't see anything like that in C++20.

I do mean that yes, and the ones I am thinking of are in C++23, so it may not matter yet. I kinda assumed there's some in C++20. I do think it's helpful to disambiguate this from the rest though.

[Kyle Charbonneau]

Thanks for the clarification. Allowing the use of otherwise allowed STL types/functions that take a range as a parameter sgtm too.

[Jan Wilken Dörrie]

Allowing range algorithms LGTM, eventually replacing base::ranges with std::ranges was an explicit goal of mine when initially adding the algorithms to base.

A few comments below.

On Tuesday, November 14, 2023 at 4:46:30 PM UTC+1 Kyle Charbonneau wrote:

Thanks for the clarification. Allowing the use of otherwise allowed STL types/functions that take a range as a parameter sgtm too.

On Tue, Nov 14, 2023 at 9:38 AM Dana Jansens <dan...@chromium.org> wrote:

On Tue, Nov 14, 2023 at 9:26 AM Kyle Charbonneau <kyle...@chromium.org> wrote:

1 + 3 sgtm.

 

2. ranges overloads, such as a ctor or method that takes a range-concept-matching object (such as a container or view) instead of taking iterator pairs.

Just to clarify, do you mean range overloads provided from allowed STL types/functions or user implemented range overloads? 

Does the STL make use of ranges anywhere outside of <range> and range based algorithms in C++20? I see that C++23 adds range based constructors/methods to STL container types but I don't see anything like that in C++20.

I do mean that yes, and the ones I am thinking of are in C++23, so it may not matter yet. I kinda assumed there's some in C++20. I do think it's helpful to disambiguate this from the rest though.

 

On Mon, Nov 13, 2023 at 4:07 PM Dana Jansens <dan...@chromium.org> wrote:

Hello,

C++20 approval has excluded "ranges" however I want to break the ranges idea into three separate parts:

1. ranges algorithms, found in the <algorithms> header: https://en.cppreference.com/w/cpp/algorithm/ranges

nit: Some of these algorithms are also in the <memory> and in C++23 in the <numeric> header. For consistency these should be allowed, too.

 

These algorithms depend on the concept of ranges (which we can loosely think of as containers or views with begin/end method pairs).

These provide strictly better and safer APIs than the traditional iterator-pair algorithms. I am aware of no concerns with using these better algorithms. And I think we should allow them.

We also model some of these in base::ranges, and we should migrate those.

+1. I tried to document the differences between base::ranges and std::ranges here. Removing these gaps would be great.

Note: I forgot to mention std::ranges::dangling in the return types section. As Anton mentioned, this allows to catch some lifetime bugs at compile time, which is great. However, it does mean that callers will indirectly be exposed to a type that only exists in <ranges>. Also we likely want to disable dangling for base::span, similarly to how it's done for std::span. This will require an explicit instantiation of the range types proposed to be banned below.

 

2. ranges overloads, such as a ctor or method that takes a range-concept-matching object (such as a container or view) instead of taking iterator pairs.

Like 1 above, these are strictly better and safer API overloads, and we should encourage their use. These are not part of "the ranges library" and are methods found on other types. So they may not have been excluded but they depend on the concept of ranges, so I think we should explicitly allow them.

+1. I would also like to explicitly allow std::ranges:: types and functions found outside the <ranges> header, such as the range access functions, iterator operations or comparison functors. These are useful in generic contexts when implementing these overloads.

 

3. ranges types, found in <ranges>: https://en.cppreference.com/w/cpp/header/ranges

These are new library types that provide functional/iterator-based programming primitives. There are concerns about correctness (e.g. borrowed_range is wrong for non-std view types), compile times, and legibility (e.g. with the | operator, which suffers similar problems as streams) with these types, and we should not allow them at this time.

+1, but do note that you are able to specialize std::ranges::enable_borrowed_range to get your own view types to behave correctly. Agreed on the other issues with std::views, though. 

[Dana Jansens]

Thanks, that all sounds good to me too.

[Peter Kasting]

Reviving this.

Seems like we have consensus to do the following:

• Allow usage of std::ranges::xxx methods outside <ranges>:
  • Algorithms in <algorithm>
  • Comparison functions in <functional>
  • Access functions in <iterator>
  • Uninitialized storage handling in <memory>
  • Once we have C++23,
    • Range-constructors and range-based functions in other containers, e.g. <vector>
    • Algorithms in <numeric>
• Convert usage of base::ranges::xxx to std::ranges::xxx and remove base/ranges
  • Will not be fully mechanical
  • Need to file a bug on this
• Specialize std::ranges::enable_borrowed_range to true for base::span to disable std::ranges::dangling for it
  • Any other types we need to do this for?
• Specialize std::ranges::enable_view to true for base::span to tell range algorithms it's O(1) to construct/copy/move
  • Technically y'all didn't discuss this but it seems clearly correct to me
  • Any other types we need to do this for?
• Ban <ranges>
  • Significant compile-time hit
    • Will this still be true if we get modules?
  • Generated code can be more challenging to optimize
  • Subjective: overloading | may be hard to read
  • The actual facilities provided are useful but not the most common sort of thing in Chromium
  • No replacement proposal at this time; both internal and external alternatives are in various states of development

Did I miss anything? Any further discussion? If I hear nothing by EOD Jan 12 I'll try to move forward with the above.

PK

[Dana Jansens]

On Tue, Jan 9, 2024 at 12:42 PM Peter Kasting <pkas...@chromium.org> wrote:

Reviving this.

Seems like we have consensus to do the following:

• Allow usage of std::ranges::xxx methods outside <ranges>:
  • Algorithms in <algorithm>
  • Comparison functions in <functional>
  • Access functions in <iterator>
  • Uninitialized storage handling in <memory>
  • Once we have C++23,
    • Range-constructors and range-based functions in other containers, e.g. <vector>
    • Algorithms in <numeric>
• Convert usage of base::ranges::xxx to std::ranges::xxx and remove base/ranges
  • Will not be fully mechanical
  • Need to file a bug on this
• Specialize std::ranges::enable_borrowed_range to true for base::span to disable std::ranges::dangling for it
  • Any other types we need to do this for?

Won't hurt to do this, but we should still not use std::ranges::borrowed_range given it will say the dangerous thing (false) by default. I am proposing a base replacement here: https://chromium-review.googlesource.com/c/chromium/src/+/5166268/4/base/ranges/is_borrowed_range.h

• Specialize std::ranges::enable_view to true for base::span to tell range algorithms it's O(1) to construct/copy/move
  • Technically y'all didn't discuss this but it seems clearly correct to me
  • Any other types we need to do this for?
• Ban <ranges>
  • Significant compile-time hit
    • Will this still be true if we get modules?

Yeah this is template instantiation making things slow, not header parsing.

[John Admanski]

I have a followup question to this discussion, that came up in the context of clang-tidy and modernize-loop-convert, which is one of the checks we make use of.

The clang-tidy modernize-loop-convert check will suggest converting old style manual iteration using rbegin+rend over to using a range-based for loop. This is done by making use of std::ranges::reverse_view. However, my interpretation of this discussion is that because that view comes from <ranges> it is not actually allowed. This isn't necessarily a big problem because I do see that we have a base::Reversed adapter which would work as a replacement in this context.

My questions would be:

1. Am I correct in my inference that std::ranges::reverse_view is considered to be banned?

2. If the answer to 1 is "yes", should we be configuring clang-tidy to suggest the use of base::Reversed instead of reverse_view?

[Peter Kasting]

(1) yes, and (2) I thought it already was, so if that changed that was an oversight. You could probably dig through the .clang-tidy history and figure out when this flipped.

PK

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/a392900b-b702-48fb-907c-94e5f64cb4b7n%40chromium.org.

[John Admanski]

My understanding is that the modernize-loop-convert parameters intended to customize how the reverse iteration would happen did not work properly with pre-C++20 and so the fixes had to be disabled entirely for reverse loops. When C++20 was finally adopted disabling of the check was simply removed.

[George Burgess]

Yeah, it was originally my impression that the suggestion of `base::Reversed` was a workaround while we didn't have C++20, rather than specific style guidance _even after_ `-std=c++20` was adopted across the board. That's my mistake then - I'll revive https://chromium-review.googlesource.com/c/chromium/src/+/4134765 with updates to reflect this discussion.

George

--

Folks have varying work hours; if I caught you outside of yours, please don't feel pressured to respond immediately.

[Peter Kasting]

Something I just ran into: <ranges> defines the concept std::ranges::range, which is "a range-like type" -- one for which it's possible to instantiate std::ranges::begin()/end(). This seems generally useful and OK as a concept to constrain range-accepting algorithms, but it's unfortunately in <ranges>. We have a couple of choices:

1. Allow <ranges>, but ban most things inside it.
2. Continue to ban <ranges>, except for some base header that #includes <ranges> and exposes base::range as a concept that means the same thing.
3. Define our own range concept that means the same thing.

I think (1) and (2) are probably bad if we're worried about compile times and leakage of banned things from <ranges>. So I reluctantly conclude we should do (3) (as needed)?

PK

[David Benjamin]

Do we know where the compiler time problems come from? Is it that the ranges header is very big, or that some particular ranges APIs cause a lot of template instantiations when used?

If the problem is that the header is big, that ship has sailed. Much of the ranges library is installed into <algorithm> and depends on those same concepts.

https://source.chromium.org/chromium/chromium/src/+/main:third_party/libc++/src/include/algorithm;l=1885-1973?q=file:algorithm$%20file:%5Ethird_party%2Flibc&ss=chromium

C++23 goes further and adds (much needed!) ranges methods to various containers that also use those concepts:

https://source.chromium.org/chromium/chromium/src/+/main:third_party/libc++/src/include/__ranges/container_compatible_range.h;drc=83eba26f311de69e205bd79b5bb16c231acf51ea;l=26

https://source.chromium.org/chromium/chromium/src/+/main:third_party/libc++/src/include/vector;drc=d3a59f71e6f32a5556c084eef6465f756196f56b;l=1980

So we're paying for much of this anyway. (If that's the cost, all the more reason to invest in C++20 modules.)

If the problem is certain patterns, we could specifically ban those patterns. Though if the rest of the STL is going in that direction, I suspect divergence here will become increasingly expensive. (Are there examples of code patterns where the compile-times are bad, relative to the non-ranges version, so we can file a ticket with libc++?)

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/210367e4-9744-4375-a9ab-625050e45db6n%40chromium.org.

[Peter Kasting]

On Wed, Feb 21, 2024 at 12:59 PM David Benjamin <davi...@chromium.org> wrote:

Do we know where the compiler time problems come from? Is it that the ranges header is very big, or that some particular ranges APIs cause a lot of template instantiations when used?

I think it's many things. I know resolving overloaded operator|()s is one specific compile-time concern. Template instantiations are another. And yes, in general, C++20 headers got even bigger and <algorithm>, which was already slow, has become even slower.

Probably the first two of those aren't bad unless we actually start using views and chaining things, which I doubt will happen (or at least, no time soon). And you're right, the third is something we already pay for.

So, maybe I was wrong, and we should allow parts of <ranges>:

• Concepts (e.g. ranges::range)
• Primitives (e.g. ranges::iterator_t)
• Dangling iterator handling? (e.g. ranges::dangling)
• Customization point objects? (e.g. ranges::begin)

For now, I'm sure we should ban adaptors (e.g. ranges::filter_view); we should probably ban factories (e.g. ranges::iota_view); we should maybe ban views (e.g. ranges::subrange), enumerations (ranges::subrange_kind) and helpers (e.g. tuple_size<ranges::subrange>).

PK

[Peter Kasting]

On Monday, March 11, 2024 at 6:53:20 PM UTC-7 pkas...@google.com wrote:

So, maybe I was wrong, and we should allow parts of <ranges>:

• Concepts (e.g. ranges::range)
• Primitives (e.g. ranges::iterator_t)
• Dangling iterator handling? (e.g. ranges::dangling)
• Customization point objects? (e.g. ranges::begin)

For now, I'm sure we should ban adaptors (e.g. ranges::filter_view); we should probably ban factories (e.g. ranges::iota_view); we should maybe ban views (e.g. ranges::subrange), enumerations (ranges::subrange_kind) and helpers (e.g. tuple_size<ranges::subrange>).

This came up today in a CL of dcheng's I was reviewing, which switched `base::ranges::{begin,end}()` to `std::{begin,end}()`, when IMO the better switch would have been to `std::ranges::{begin,end}()` (but that's not formally allowed today). The ranges versions of these don't just provide a customization point -- they also work transparently on more types and prevent various unsafe uses (e.g. attempting to instantiate an lvalue iterator from a borrowed range, a la `auto it = std::ranges::begin(ReturnsATemp());`).

Based on my thinking-out-loud above, I feel more convinced we should allow <ranges> and std::ranges:: use but ban all of the following:

• All use of `std::ranges::views` and its shorthand alias `std::views`
• Views, i.e. `ranges::view_interface` and `ranges::subrange`
• Factories and adaptors, i.e. everything that matches the regex `\branges::\w+_view\b`
  • I think this won't fire on specializations of `std::ranges::enable_view` for our types (because the strings `ranges` and `enable_view` wouldn't be joined), which is good
• Enumerations, i.e. `ranges::subrange_kind`

There is no need to attempt to ban the range-related helpers, as they're just specializations of pre-existing templates for range-related types we ban above.

My hope is that doing the above allows the "useful parts" of ranges without the "template instantiation/overload resolution explosion" problems that lead to long compiles; and is specific enough to be codified in a PRESUBMIT check. We could say that chaining operations using `|` is banned, but I think if views/factories/adaptors are banned people can't do it anyway, and it would be hard to write a PRESUBMIT to check that.

I'd appreciate feedback on this proposal, especially if I've overlooked something. Use of std::ranges:: is already creeping in, so we should codify something.

PK

[Daniel Cheng]

This sounds reasonable to me, with a few minor thoughts. Just to re-enumerate what this would allow (based on filtering out what's explicitly disallowed above from cppreference):

1. the various range concepts, e.g. std::ranges::borrowed_range, std::ranges::sized_range, et cetera.

2. the various range "primitives" (that's what cppreference calls it), e.g. std::ranges::range_iterator_t<R> instead of having to write decltype(std::ranges::begin(...)).

3. dangling iterators: prevents bugs like (example from cppreference):
    auto get_array_by_value = [] { return std::array{0, 1, 0, 1}; };
    auto dangling_iter = std::ranges::max_element(get_array_by_value());
    // dangling_iter is of type std::ranges::dangling and can't be dereferenced. This is good!
  I expect most 'normal' code won't really need to deal with this type directly anyway, except when there's a mistake :).

4. customization points: these seem fine, e.g. std::ranges::begin() and friends.

5. enumerations, specifically std::ranges::subrange_kind. I think we probably don't need this, given the ban on subranges and views?

6. miscellaneous helpers for subranges for std::get() and std::tuple_size and std::tuple_element.

1-4 all seem non-controversial.

Might be good to disallow 5 (even though I don't expect it to really come up). 6 is presumably implicitly disallowed and won't really come up if we're not using subranges.

Daniel

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/968fbbeb-6100-4f1d-a2ba-b9a97738a48bn%40chromium.org.

[Peter Kasting]

I suggesting banning subrange_kind (your #5), so I'm in agreement there. And yes, the things in #6 should be moot because we won't be using those types. 

PK

[danakj]

On Thu, May 9, 2024 at 9:16 PM Peter Kasting <pkas...@chromium.org> wrote:

I suggesting banning subrange_kind (your #5), so I'm in agreement there. And yes, the things in #6 should be moot because we won't be using those types. 

PK

On Thu, May 9, 2024, 5:06 PM Daniel Cheng <dch...@chromium.org> wrote:

This sounds reasonable to me, with a few minor thoughts. Just to re-enumerate what this would allow (based on filtering out what's explicitly disallowed above from cppreference):

1. the various range concepts, e.g. std::ranges::borrowed_range, std::ranges::sized_range, et cetera.

We should not use borrowed_range, which has the wrong default, saying ranges it does not know about are _not_ borrowed, which easily makes generic code do bad things, moving out of references. We can provide our own better one: https://chromium-review.googlesource.com/c/chromium/src/+/5166268/4/base/ranges/is_borrowed_range.h

While still acknowledging the stdlib does use it so using enable_borrowed_range is important, but writing our own generic code it's better to not inherit bugs on legacy view-type ranges/collections.

The others are fine AFAIK.

 

2. the various range "primitives" (that's what cppreference calls it), e.g. std::ranges::range_iterator_t<R> instead of having to write decltype(std::ranges::begin(...)).

SGTM

 

3. dangling iterators: prevents bugs like (example from cppreference):
    auto get_array_by_value = [] { return std::array{0, 1, 0, 1}; };
    auto dangling_iter = std::ranges::max_element(get_array_by_value());
    // dangling_iter is of type std::ranges::dangling and can't be dereferenced. This is good!
  I expect most 'normal' code won't really need to deal with this type directly anyway, except when there's a mistake :).

Yep

 

4. customization points: these seem fine, e.g. std::ranges::begin() and friends.

Yes please

 

5. enumerations, specifically std::ranges::subrange_kind. I think we probably don't need this, given the ban on subranges and views?

Agree not needed, not sure how it would show up given we have no subrange (it's a view)

 

6. miscellaneous helpers for subranges for std::get() and std::tuple_size and std::tuple_element.

These are fine, and are implicitly called so we don't need to think about it right?

[Peter Kasting]

On Fri, May 10, 2024 at 7:03 AM danakj <dan...@chromium.org> wrote:

On Thu, May 9, 2024 at 9:16 PM Peter Kasting <pkas...@chromium.org> wrote:

On Thu, May 9, 2024, 5:06 PM Daniel Cheng <dch...@chromium.org> wrote:

1. the various range concepts, e.g. std::ranges::borrowed_range, std::ranges::sized_range, et cetera.

We should not use borrowed_range, which has the wrong default, saying ranges it does not know about are _not_ borrowed, which easily makes generic code do bad things, moving out of references. We can provide our own better one: https://chromium-review.googlesource.com/c/chromium/src/+/5166268/4/base/ranges/is_borrowed_range.h

Wait, I'm confused.  The way the STL defines "borrowed range", it means "the underlying storage is assumed to safely outlast this object, so if I take iterators from it, they'll still be valid even if the object I took them from is destroyed". Returning "false" seems like the correct default for that definition of "borrowed range", since "false" means "you can only assume the iterators are dereferenceable while the object is still in scope".

What are specific instances where this is wrong? You mention some specific problems like moving out of references; is there an example to look at?

PK

[danakj]

Since std iterators have no concept of rvalues, you must move out of an lvalue reference. If you have a view type and you move out of it, you leave behind an owning container in an unexpected state.

Here's a simple example of what I mean:

std::vector<U> owning;

std::span<U> view = owning;  // pretend span would say borrowed = false, the default. this is true for example with view types in llvm.

template <class T>

void moves_out(T range) {

  if constexpr (!std::ranges::borrowed_range<T>) {

    // As an optimization we can move from the values as we own the range and will destroy it!

    for (auto& x: range) { stuff(std::move(x)); }  // oops we moved out of the vector not the span, so now the Us will be use-after-move.

  } else {

    // The range is a view we copy things out.

    for (auto& x: range) { stuff(x)); }

  }

}

This may sound contrived but this was the source of a UAF bug in Subdoc, which is why it's now burned into my head.

 

PK

[Peter Kasting]

This looks like a misuse of borrowed_range to me. That concept says nothing about whether the data under the iterators can be freely modified (i.e. "no one else has a reference to this data"), which is what you'd need to write that move optimization. It only speaks to whether you will be able to read from the iterators after the object you got them from is gone. 

Does the STL itself misuse this concept in this way? I'm sympathetic to an argument of "no, but it's easy to misunderstand this", but creating our own concept of the same name with a distinct meaning compounds the confusion. 

PK

[danakj]

On Wed, May 22, 2024 at 3:35 PM Peter Kasting <pkas...@chromium.org> wrote:

This looks like a misuse of borrowed_range to me. That concept says nothing about whether the data under the iterators can be freely modified (i.e. "no one else has a reference to this data"), which is what you'd need to write that move optimization.

The code here owns the range, so it knows through local analysis that no other code has a reference to it.

 

It only speaks to whether you will be able to read from the iterators after the object you got them from is gone. 

Does the STL itself misuse this concept in this way?

So little of the STL uses ranges at all, nothing really before C++23, and there's just a few new ctors/methods? I am not aware of any but I doubt it (yet, anyway).

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFBs7BZqi_22S7fvP-9WVNu2NGikie27WbUp9Y-h8ps19A%40mail.gmail.com.

[Peter Kasting]

On Wed, May 22, 2024, 12:40 PM danakj <dan...@chromium.org> wrote:

On Wed, May 22, 2024 at 3:35 PM Peter Kasting <pkas...@chromium.org> wrote:

This looks like a misuse of borrowed_range to me. That concept says nothing about whether the data under the iterators can be freely modified (i.e. "no one else has a reference to this data"), which is what you'd need to write that move optimization.

The code here owns the range, so it knows through local analysis that no other code has a reference to it.

It owns the range, but not the underlying data. It can't do analysis on who else might have a reference to that, and borrowed_range does not tell it that it can. 

PK

[danakj]

"The concept borrowed_range defines the requirements of a range such that a function can take it by value and return iterators obtained from it without danger of dangling."

I think I am saying that if it's not borrowed, the iterators dangle because you've destroyed the owning container.

I think you're saying that it's logically allowed to not dangle even though it says not-borrowed-range.

To me, that makes it a really dangerous tool that is an easy footgun.

[Peter Kasting]

Being borrowed only tells you that someone else definitely owns the backing store the iterators point into, so you can make the additional optimization of dropping the range early instead of having to keep it alive past any calls using the iterators. But it doesn't tell you about the data within that store. Even if the type is not a borrowed range, maybe the range holds a ref to the data, so the type alone does not tell you whether anyone else can access this data. Maybe the iterators came transitively from another source, so this type cannot guarantee their provenance.

The intent is that "borrowed" is the optimizable case, rather than "not borrowed". What you're looking for sounds a bit more like "is a sole ownership type".

To me, that makes it a really dangerous tool that is an easy footgun.

I don't know that I agree. It doesn't have the sort of subtle action at a distance that [[no_unique_address]] does. It's simply meant for a single narrow optimization case: if the range borrows, you can drop it once you've gotten the iterators.

PK

[danakj]

On Thu, May 23, 2024 at 10:19 AM Peter Kasting <pkas...@chromium.org> wrote:

On Wed, May 22, 2024, 12:47 PM danakj <dan...@chromium.org> wrote:

On Wed, May 22, 2024 at 3:42 PM Peter Kasting <pkas...@chromium.org> wrote:

On Wed, May 22, 2024, 12:40 PM danakj <dan...@chromium.org> wrote:

On Wed, May 22, 2024 at 3:35 PM Peter Kasting <pkas...@chromium.org> wrote:

This looks like a misuse of borrowed_range to me. That concept says nothing about whether the data under the iterators can be freely modified (i.e. "no one else has a reference to this data"), which is what you'd need to write that move optimization.

The code here owns the range, so it knows through local analysis that no other code has a reference to it.

It owns the range, but not the underlying data. It can't do analysis on who else might have a reference to that, and borrowed_range does not tell it that it can. 

"The concept borrowed_range defines the requirements of a range such that a function can take it by value and return iterators obtained from it without danger of dangling."

I think I am saying that if it's not borrowed, the iterators dangle because you've destroyed the owning container.

I think you're saying that it's logically allowed to not dangle even though it says not-borrowed-range.

Being borrowed only tells you that someone else definitely owns the backing store the iterators point into, so you can make the additional optimization of dropping the range early instead of having to keep it alive past any calls using the iterators. But it doesn't tell you about the data within that store. Even if the type is not a borrowed range, maybe the range holds a ref to the data, so the type alone does not tell you whether anyone else can access this data. Maybe the iterators came transitively from another source, so this type cannot guarantee their provenance.

The intent is that "borrowed" is the optimizable case, rather than "not borrowed". What you're looking for sounds a bit more like "is a sole ownership type".

Yeah, probably the "is const transitive" could be called is_owning_range then rather than using the same name, which would address your concern about having overlapping names.

To me, that makes it a really dangerous tool that is an easy footgun.

I don't know that I agree. It doesn't have the sort of subtle action at a distance that [[no_unique_address]] does. It's simply meant for a single narrow optimization case: if the range borrows, you can drop it once you've gotten the iterators.

Not all footguns are as bad as totally breaking our idea of what memory an object covers. :) But probably not the best use of time to go on too long about what I think are poor design choices and defaults in std that cause easy programming mistakes.

 

PK

[Peter Kasting]

Maybe the important thing for this thread is just concluding whether we need to ban/rewrite anything related to borrowed ranges. I don't think we do, we just need to be narrow in our use of that concept to optimize. Do you agree? 

PK

[danakj]

On Thu, May 23, 2024 at 11:23 AM Peter Kasting <pkas...@chromium.org> wrote:

Maybe the important thing for this thread is just concluding whether we need to ban/rewrite anything related to borrowed ranges. I don't think we do, we just need to be narrow in our use of that concept to optimize. Do you agree? 

Yeah, sgtm.

[Peter Kasting]

Ok. Then I think that resolves things. I consider Daniel's/my summary to cover what we decided. I will try to get to updating our guidance "soon". (Really! I promise!)

PK

--
You received this message because you are subscribed to a topic in the Google Groups "cxx" group.
To unsubscribe from this topic, visit https://groups.google.com/a/chromium.org/d/topic/cxx/ZnIbkfJ0Glw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cxx+uns...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAHtyhaQjfG%2BvqTsMz7gZO7c08x%2B%2B%3DdfSJYJY1rtkvT1sw_op-Q%40mail.gmail.com.