3

I would like to share a few "footguns" discovered over my (brief) course of using range-v3

1: Views::filter memory corruption

sourceRange | views::filter(predicate) | ranges::to<...>();

For some reason, this can invoke filter multiple times. Which is dandy when filter is pure and deterministic, but not when it's nondeterministic.

I recently discovered a problematic filter predicated on the current system time, which was liable to shift across multiple invocations on the same element. One invocation would filter it, the next would keep it. The result: an insidious crash, as the ranges::to implementation seemingly filters in two passes in this particular case:

  • The first pass: to determine the resultant size of the target converted container. In order to preallocate a buffer

  • The second pass: to actually determine elements to fill the preallocated buffer

The insidious part: if the second filtration pass permits more elements through than the first, the preallocated buffer would silently overflow with no checks.

2: Multiple Invocation of views::transform

  • See related question here

In some situations (in conjunction with views::filter or views::remove_if that I am aware of), views::transform can potentially be invoked multiple times per element.

Again, this is totally fine if transform is deterministic without side-effects on the source range. But it is distinctly not so if it mutates the source range in a non-idempotent manner. Suppose:

sourceRangeOfA 
  | views::move 
  | views::transform(convertByMoveToB) 
  | views::filter(somePredicate)

Clearly, multiple invocations of transform on the same element can be disastrous.

My Question

I want to love and continue using ranges, I really do. But some of these bugs were tough lessons to learn and particularly painful to troubleshoot. What's particularly hard to swallow here: rewriting the two above examples in an iterative style completely resolves the problems. Which seems backwards: ranges should be safer, not more dangerous.

What I ask is -- what other footguns abound, and what lessons can we draw from this?

  • Should all mutations (e.g views::transform) be deterministic and const with respect to elements on which they are applied?
    • This obviously precludes views::move, so we are trading off performance to use range-v3. It doesn't feel like a great tradeoff
    • The alternative is views::cache1. My gripe with this is that it's sometimes not immediately intuitive when potentially needed - especially to range newbies. And if you forget it - disaster looms'
  • Otherwise, if I really wanted non-const transforms, what other views do I need to watch for which are dangerous in conjunction (like filter)
  • What other view adapter combinations are problematic and lurking footguns?
  • Should filter always be pure and deterministic?
  • Should filter or any "filtration" style range ever be used with transform?
  • Why aren't these footguns captured in the documentation?
  • Can std::ranges do better?
5
  • Why not use std-ranges?
    – 康桓瑋
    Commented Jul 8 at 6:26
  • The filter issue is noted in the reference for std::views::filter: "Modification of the element denoted by this iterator is permitted, but results in undefined behavior if the resulting value does not satisfy the filter's predicate.". Your non-idempotent transform isn't called out specifically, but it isn't hard to reason from the description of operator*
    – Caleth
    Commented Jul 8 at 9:38
  • Also note that ranges::to isn't the thing that specifies the two passes, it's specifically std::vector's constructor. Other std containers don't fetch the size first.
    – Caleth
    Commented Jul 8 at 9:46
  • @Caleth Modification of the element denoted by this iterator is permitted.... Can you help me understand how this explains the first filter example? - To somebody who is not familiar with implementation internals (vast majority of ranges audience) How specifically is the iterator's pointed element being modified here? What I am guessing here is that the iterator is being dereferenced twice per element - once from operator++ for vec.reserve(), and again later. I don't see the connection to this clarifying comment
    – Harrison
    Commented Jul 8 at 10:03
  • Indirect hints: - nothing says the filter is applied only once - the sentence about modification only makes sense if the filter can be applied multiple times - the concepts (like forward_range) are copied from the underlying range - the predicate must satisfy indirect_unary_predicate and thus *i must be equality-preserving. Even the legacy input iterator concept requires that (void)*i,*i be equivalent to *i, so we seem to be missing a weaker notion of range. Yes, this is all rather error-prone :-( Commented Jul 8 at 11:13

0

Browse other questions tagged or ask your own question.