false positive with std::list::splice invalidated iterator in a loop

[oschonrock]

Thank you for your fantastic work on -Wlifetime!

I have extracted and minimized an example from real code of what I think is a false positive.

Warning diagnostic shown by experimental -Wlifetime on godbolt:

<source>:14:28: warning: passing a dangling pointer as argument [-Wlifetime]

       iter = std::find_if(iter, origin.end(), predicate)) {

    

This is the example on godbolt.

Code also below.

I think that line15 means that the iterator does not dangle (that is why line 15 is there).
But I think that -Wlifetime cannot follow the loop logic? Although I thought I saw in one of your talks that it does "1st iteration" and "all other iterations", which would mean it could hypothetically work this out?

Or it is that -Wlifetime disagrees with my interpretation of which iterators get invalidated:

No iterators or references become invalidated, the iterators to moved elements remain valid, but now refer into *this, not into other.

https://en.cppreference.com/w/cpp/container/list/splice

My code assumes that iterators to elements not moved remain valid. Only one element (*iter) is splice moved to destination on each iteration. ie line 15 iter_next = std::next(iter) should provide (via line 17) a non dangling value of iter for the 2nd and subsequent loop iterations?

Am I being Unrealistic? Needs annotating? How?

Code (same as on godbolt above).

#include <algorithm>
#include <list>
#include <iostream>

template <typename T, typename UnaryPredicate>
void move_append_if(
    std::list<T>& origin, 
    std::list<T>& destination,
    UnaryPredicate&& predicate) {

  for (auto iter = std::find_if(origin.begin(), origin.end(), predicate);
       iter != origin.end();
       iter = std::find_if(iter, origin.end(), predicate)) {
    auto iter_next = std::next(iter);
    destination.splice(destination.end(), origin, iter);
    iter = iter_next;
  }
}

int main() {
  auto o = std::list<int>{1,3,11,12,13,4,5,15};
  auto d = std::list<int>{};
  move_append_if(
      o, d, [&](const auto& e) { return e < 10; });

    for (auto e: o) {
        std::cout << e << " ";
    }
    std::cout << '\n';

    for (auto e: d) {
        std::cout << e << " ";
    }
    std::cout << '\n';
}

[Xazax-hun]

Thanks for reporting this!

There are actually multiple problems here. The lifetime analysis does not have knowledge about splice, so it has some really dumb heuristics and concludes that it must invalidate the owner. This part is easy to fix, we either need to annotate splice as lifetime_const or hardcode this knowledge into the check.

The other part is the moving. Unfortunately, we did not implement support for move operations yet. I think, currently, this is out of reach for the lifetime analysis, and you can use gsl::suppress annotation to suppress the analysis for the function. Hopefully, once we have move support in place, we can analyze this without any issues.

[Xazax-hun]

I committed 0ce090b

This does not fix the modeling of lists completely, but it makes using them a bit less painful.

[oschonrock]

Thank you! But is this splice actually a move? I am trying to imagine what happens during a list.splice and it's just a that a bunch of pointers get moved around right? Is this semantically the same as a "move"? I guess it is, in the sense that the "owner of that element has now changed" without making a "copy".

[Xazax-hun]

Unfortunately, this specific issue is not solved by that commit.

I think the best way to describe what splice does on the more abstract level is to transfer ownership. In the implementation it is only about rewiring some pointers, right. But actually, when you move a vector, something very similar will happen. The implementation just rewires some pointers and the buffer will stay in place. So your description is quite accurate.

Modeling splice is quite a challenge though, as lifetime analysis has no knowledge which element does an iterator point to. So I am not sure if we will ever have a 100% solution to this problem. :(