Can a mutable filter view be a forward range?

[ericniebler]

Imagine the following:

std::vector<int> vec{1,2,3,4,5,6,7,8,9};
auto odds = vec | view::filter([](int i) { return i & 1; });
auto iter = ranges::next(odds.begin()); // *iter == 3
*iter = 4; // no longer odd!
assert(iter == ranges::next(odds.begin())); // Fails!

This shouldn't be allowed to fail. I suspect we either need to make mutable filter views single-pass, or else make them immutable, or else offer both options with different names.

I suspect there are other views with this problem.

[ericniebler]

ATTN @CaseyCarter

[ericniebler]

\<queue discussion about how to detect whether an iterator's reference type is mutable when it could be a proxy>

[CaseyCarter]

I suspect we either need to make mutable filter views single-pass

I actually thought that filter was already single-pass for exactly this reason. A third option would be to add blanket wording covering the interaction between mutable elements and ranges whose contents are value-dependent, forbidding multipass access after mutation, or forbidding multipass access only in combination with mutations that could affect the selection of elements. *iter = 27;, e.g., would be fine in the example.

[ericniebler]

A third option would be to add blanket wording covering the interaction between mutable elements and ranges whose contents are value-dependent, forbidding multipass access after mutation

Yeah, that occurred to me. On the one hand, dropping the category to input feels overly nannying (and very limiting), not doing that feels like a subtle bug farm.

From a practical perspective, I'm not even sure how to change filter to detect that it's returning a mutable reference until we know how to characterize proxy references. I guess now that we've fixed ericniebler/stl2#381, we can test Writable<iterator_t<Rng>, value_type_t<Rng>> or something. If we decide the answer is to change filter to return a non-mutable reference, we can't do that without building out better support for manipulating proxy types.

I'm inclined to fix this by saying "don't do that".

[gnzlbg]

Could we have two filters? That is, one allowing mutation and one disallowing it? Ifthe price to keep things simpler is to have two different methods I think that is a price worth paying.

On Sat 1. Jul 2017 at 20:44, Eric Niebler notifications@github.com wrote:

A third option would be to add blanket wording covering the interaction between mutable elements and ranges whose contents are value-dependent, forbidding multipass access after mutation

Yeah, that occurred to me. On the one hand, dropping the category to input feels overly nannying (and very limiting), not doing that feels like a subtle bug farm.

From a practical perspective, I'm not even sure how to change filter to detect that it's returning a mutable reference until we know how to characterize proxy references. I guess now that we've fixed ericniebler/stl2#381 https://github.com/ericniebler/stl2/issues/381, we can test Writable<iterator_t, value_type_t> or something. If we decide the answer is to change filter to return a non-mutable reference, we can't do that without building out better support for manipulating proxy types.

I'm inclined to fix this by saying "don't do that".

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ericniebler/range-v3/issues/684#issuecomment-312449003, or mute the thread https://github.com/notifications/unsubscribe-auth/AA3Npn8u3Y-PQGQ781DBL2ExEF_-Sey2ks5sJpORgaJpZM4OKzUe .

-- Dipl.-Ing. Gonzalo Brito Gadeschi Institute of Aerodynamics and Chair of Fluid Mechanics RWTH Aachen University Wuellnerstraße 5a D-52062 Aachen Germany Phone: ++49-(0)241-80-94821 Fax: ++49-(0)241-80-92257 E-mail: g.brito@aia.rwth-aachen.de Internet: www.aia.rwth-aachen.de

[CaseyCarter]

Could we have two filters? That is, one allowing mutation and one disallowing it? If the price to keep things simpler is to have two different methods I think that is a price worth paying.

Would your opinion of "simpler" change if we replace "filter" with "every view or sentinel type whose behavior depends on the value of elements"? view::c_str, view::delimit, view::drop_while, view::group_by, view::replace, view::replace_if, view::take_while, view::unique, ...all the set algorithm views... is tokenize multipass?

[Peregring-lk]

This problem is not only related with the contents of the view itself, but also with the size of the generated range. It's like an iterator saving a shared_ptr to another iterator, even if the proxy iterator is not mutable. I saw that example in a standard library issue.

Every copied iterator will share the inner iterator. Incrementing a previous copy of a iterator from the same range will increment all iterators, which can be seen as a change to the view's size (any copy is a step closer to the end) and the views contents without writting to the iterator.

So the mutability of the range is not only related with the mutability of its iterator type when dealing with proxies. Besides, writting to value-dependents not necesarily changes the filter condition, so the condition is that the filter functor must be "equality preserving" after writting or something like that.

[CaseyCarter]

FWIW: [range.filter.iterator]/1 in the C++20 working draft now states: "Modification of the element a filter_view::iterator denotes is permitted, but results in undefined behavior if the resulting value does not satisfy the filter predicate." This overly-draconian restriction is the result of LWG discussion: we decided the safest thing to do for now was avoid the problem while leaving ourselves room to clear things up later.

[cjdb]

"Modification of the element a filter_view::iterator denotes is permitted, but results in undefined behavior if the resulting value does not satisfy the filter predicate."

IIUC this means that

auto v = std::vector{0, 1, 2, 3, 4};
auto f = v | view::filter(is_even);
++v[1] ; // okay

auto i = begin(f);

*i += 2; // okay
++v[0]; // UB?
++*i; // UB

[CaseyCarter]

IIUC this means that

auto v = std::vector{0, 1, 2, 3, 4};
auto f = v | view::filter(is_even);
++v[1] ; // okay

Yes.

auto i = begin(f);

*i += 2; // okay

Yes.

++v[0]; // UB?

Since you made v[0] odd above, and the caching of the return value of begin is normative, v[0] is not an element of f and you can do whatever you like to it. Notably this could produce weirdness like ranges::equal(f, decay_copy(f)) == false. (filter_view isn't special here: we need to get a better handle on invalidation of views and iterators/sentinels into them in general.)

I misread: the first increment is to v[1], not v[0], so v[0] is the first element of f and this is formally UB.

++*i; // UB

Yes.

[ericniebler]

I'm making an executive decision and calling this one fixed.