CODEWITHSUNDEEP
c++c++11iteratorlanguage-lawyerundefined-behavior
TemplateRex
TemplateRex

Reputation: 70546

Undefined behavior when the offending expression is not used?

In a comment by @MarcvanLeeuwen to another Q&A, it was suggested that the following is undefined behavior (UB):

template<class FwdIt, class T>
FwdIt find_before(FwdIt before_first, FwdIt last, T const& value)
{
    return std::adjacent_find(before_first, last, 
        [&](auto const& /* L */, auto const& R) { 
        // note that the left argument of the lambda is not evaluated
        return R == value; 
    });
}

auto list = std::forward_list<int> { 1, 2 };
auto it = find_before(list.before_begin(), list.end(), 1); // undefined behavior!?

The UB comes from the fact that the BinaryPredicate that is supplied to std::adjacent_find will dereference two adjacent iterators at a time, the first pair being list.before_begin() and list.begin(). Since before_begin() is not dereferencable, this could entail UB. On the other hand, the left argument is never used inside the lambda. One might argue that under the "as-if" rule it is unobservable whether the derefence actually took place, so that an optimizing compiler might elide it altogether.

Question: what does the Standard say about dereferencing an undereferencable iterator it, when the expression *it is not actually used and could be optimized away? (or more generally, is it UB when the offending expression is not used?)

NOTE: the offending code is easy to remedy by special casing the first iterator (as is done in the updated original Q&A).

Upvotes: 1

Views: 166

Answers (3)

Werner Henze
Werner Henze

Reputation: 16771

23.3.4.3 forward_list iterators [forwardlist.iter]

iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;
const_iterator cbefore_begin() const noexcept;

1 Returns: A non-dereferenceable iterator that, when incremented, is equal to the iterator returned by begin().
3 Remarks: before_begin() == end() shall equal false.

With sentence 3 in mind, if you call adjacent_find like you do it will dereference the first iterator if there is at least one element in the list (elem1: before_begin(), elem2: begin(), end: end()).

Sentence 1 says that the iterator returned by before_begin is not dereferencable. Not. In any case. Without any if or when. It is undefined behavior to dereference the iterator, the standard is not saying you can dereference the iterator and throw away the return value of *before_begin(). Keep in mind that adjacant_find needs to dereference the iterator so it can pass whatever the dereferencing returns to your predicate.

As always with undefined behavior the compiler is free to do whatever he wants. If the compiler sees in an optimization stage that he can inline your predicate and if the thinks that the left iterator does not need to be dereferenced because you do not use the returned value, he might generate code that just does so and hence does not crash. Generating code that works like you expect is one possibility in the case of undefined behavior, but you cannot count on it.

BTW, why would you want to adjacent_find with a predicate that looks only at the right side? Wouldn't you use a findthen?

Upvotes: 1

ecatmur
ecatmur

Reputation: 157424

before_begin() yields a non-dereferenceable iterator; one for which applying unary * has undefined behavior, so certainly the above code has undefined behavior:

1.3.24 [defns.undefined]

undefined behavior
behavior for which this International Standard imposes no requirements

Now, it is certainly true that for some implementations of the library, it would be possible for the above code to have defined behavior; for example, in a simple implementation of forward_list, operator* on its iterator could have the effect of forming a T& reference to an uninitialised area of aligned storage:

template<typename T> struct forward_list {
    struct Node {
        Node* next = nullptr;
        typename aligned_storage<sizeof(T), alignof(T)>::type buf;
    };
    struct iterator {
        Node* node;
        T& operator*() { return *static_cast<T*>(static_cast<void*>(node->buf)); }
    };
    Node head;
    iterator before_begin() { return {&head}; }
};

In this scenario *(list.before_begin()) has defined behavior, as long as the result is only used in the "limited ways" allowed by 3.8p6.

However, any small change to this scenario could result in *(list.before_begin()) becoming undefined; for example, optimising for space an implementation could use a Node_base that omits storage and derive from it for the concrete list nodes. Or perhaps the aligned storage could contain an object wrapping T, so accessing the wrapped T falls foul of 3.8p6. Alternatively, a debug implementation could check for dereferencing the before-begin iterator and terminate your program.

By the as-if rule, the implementation is permitted to eliminate evaluations that have no visible side effects, but that doesn't result in your code having defined behavior. If the implementation debug-checks the dereference, program termination is certainly a side effect so is not eliminable.

More interestingly, if an operation with undefined behavior occurs on the way to forming a T& reference, then an optimising compiler is likely to use this to infer that the code paths leading up to the undefined behavior cannot occur. Per the reference implementation of adjacent_find, eliminating the code paths leading to the offending *first give the result that find_before will always return last.

Upvotes: 1

James Kanze
James Kanze

Reputation: 154007

There is clearly undefined behavior here, supposing the argument names mean what they seem to mean, but it is in the callers code. There is no such thing as an iterator before first, and just attempting to create one is undefined behavior. The undefined behavior doesn't come from attempting to dereference the iterator; it comes from its very existance. (Of course, std::adjacent_find will dereference it, before calling your lambda, so if the iterator exists, and is not dereferenceable, that is also undefined behavior.)

Upvotes: 0

Related Questions