[libc++][NFC] Add checks for lifetime issues in classic algorithms.

[var-const]

Revert local testing changes.

[var-const]

This is a follow-up to https://reviews.llvm.org/D130197 and https://reviews.llvm.org/D130212. I have manually confirmed that these tests would have found the bug fixed by those two patches.

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

10

Making this support C++03 would be pretty painful because it doesn't support initializer lists.

463

There needs to be a compromise between providing valid inputs for each algorithm and having a separate input for every single function. On one hand, the inputs have to satisfy the preconditions (or else we'd trigger undefined behavior) and exercise many (ideally all) the code paths in the algorithm (because issues are only found if they're triggered). On the other hand, having separate inputs for each algorithm is unmaintainable. The idea here is to split all algorithms into a few groups and provide a set of interesting inputs for each group (e.g. the default set, the sorted set, the partitioned set, etc.).

552

I don't know of a good way to pass a pointer to a template function, so unlike similar tests for range algorithms I'm using lambdas here.

558

I know it's a lot of TODOs, but I'd like to get some feedback before spending time on how to test algorithms with more complicated inputs. This patch already improves coverage significantly.

[var-const]

Rebase on main.

[var-const]

Fix the CI.

[huixie90]

I think this is good. But I'd like to clarify the idea behind it. IIUC, the idea is that

• there is a global object pool of ptrs
• the class's destructor removes this from the global pool
• every operation assert this is inside the pool

But if the object destructor has been run, it is UB to call its member function. and since it is UB , those assert in theory is not guaranteed to run

[var-const]

In D130330#3671468, @huixie90 wrote:

I think this is good. But I'd like to clarify the idea behind it. IIUC, the idea is that

• there is a global object pool of ptrs
• the class's destructor removes this from the global pool
• every operation assert this is inside the pool

But if the object destructor has been run, it is UB to call its member function. and since it is UB , those assert in theory is not guaranteed to run

Yes, it's true that this relies on undefined behavior. However, I think it's the pragmatic thing to do:

• I can't think of a way to do this that avoids UB, because checking an object after its destructor has run is really the crux of the problem. constexpr checks are great in that regard but unfortunately won't give us full coverage as I mentioned in another comment. So it looks like our alternatives are either having checks that rely on UB or no checks at all (for some cases, like most of std::sort which is the motivating example);
• I have manually confirmed that it works (in the sense that it does find actual lifetime issues). It would have found both the original bug that triggered the assertion in Chromium and the fact that the first patch with the fix still contained a dangling temporary;
• I have deliberately written the lifetime checks so that they never dereference this (that's one of the reasons the cache is a static variable). In practice, I presume that member function calls translate to regular function calls with this as the first parameter (simplifying a little). Neither the function code nor the _value_ of the this pointer have a reason to become invalid after the destructor has run. Now, it's possible that some compiler optimization simply prevents the member function from being called since that is supposed to be impossible (for a valid program). I'm very skeptical this could happen in practice, and even if it does, it seems like the worst that could happen is that these tests would miss a lifetime bug. While that would be unfortunate, it's not significantly worse than the status quo which is no checks at all.

Of course, I'd be happy to rewrite this if there's a way to achieve the same or similar coverage without relying on undefined behavior. Unfortunately, I can't think of one -- if you have any ideas, I'm happy to discuss.

[var-const]

Fix the CI, rebase on main.

[huixie90]

In D130330#3672322, @var-const wrote:

In D130330#3671468, @huixie90 wrote:

I think this is good. But I'd like to clarify the idea behind it. IIUC, the idea is that

• there is a global object pool of ptrs
• the class's destructor removes this from the global pool
• every operation assert this is inside the pool

But if the object destructor has been run, it is UB to call its member function. and since it is UB , those assert in theory is not guaranteed to run

Yes, it's true that this relies on undefined behavior. However, I think it's the pragmatic thing to do:

• I can't think of a way to do this that avoids UB, because checking an object after its destructor has run is really the crux of the problem. constexpr checks are great in that regard but unfortunately won't give us full coverage as I mentioned in another comment. So it looks like our alternatives are either having checks that rely on UB or no checks at all (for some cases, like most of std::sort which is the motivating example);
• I have manually confirmed that it works (in the sense that it does find actual lifetime issues). It would have found both the original bug that triggered the assertion in Chromium and the fact that the first patch with the fix still contained a dangling temporary;
• I have deliberately written the lifetime checks so that they never dereference this (that's one of the reasons the cache is a static variable). In practice, I presume that member function calls translate to regular function calls with this as the first parameter (simplifying a little). Neither the function code nor the _value_ of the this pointer have a reason to become invalid after the destructor has run. Now, it's possible that some compiler optimization simply prevents the member function from being called since that is supposed to be impossible (for a valid program). I'm very skeptical this could happen in practice, and even if it does, it seems like the worst that could happen is that these tests would miss a lifetime bug. While that would be unfortunate, it's not significantly worse than the status quo which is no checks at all.

Of course, I'd be happy to rewrite this if there's a way to achieve the same or similar coverage without relying on undefined behavior. Unfortunately, I can't think of one -- if you have any ideas, I'm happy to discuss.

Hi, thanks for the explanation. Undefined behavior is not something very reliable.
My original test has some coverage (would fail on gcc). I am trying to figure out why clang passes the test. See this reproduction example (it is basically my original test plus making Reference destructor to set _i to be nullptr
https://godbolt.org/z/Y3j4GGjxv
It is clear that the behavior of the original __iter_move is already wrong according to clang output. If the program behaves correctly, i should equal to 5 and the program should return 5. But the program return 139 which means something clearly wrong.
However, the assertion assert(i==5) isn't triggered because of the Undefined Behaviour. The compiler doesn't even bother assert as i is just rubbish value.

If we run the test with -fsantize=address, it would catch the issue
https://godbolt.org/z/q7Khc91T7

[var-const]

My original test has some coverage (would fail on gcc). I am trying to figure out why clang passes the test. See this reproduction example (it is basically my original test plus making Reference destructor to set _i to be nullptr

That's exactly my experience with compiler warnings and tools like Asan -- all of them are essentially "best effort" and aren't reliable ("reliable" in the sense "guaranteed to catch 100% of issues"). In fact, when I did the first patch to fix the Chromium issue, Clang could see the dangling temporary in the original version of __iter_move (that returned a dangling value_type) but not in the version from the patch (that returned a dangling reference), even though both were equally UB and essentially the same issue. You encountered a very similar problem where GCC sees a lifetime issue while Clang doesn't. I'm sure there exist counterexamples where Clang would catch something that GCC cannot spot. The point is, these warnings aren't meant to validate that the code is correct -- while their presence almost always indicates a problem, their absence doesn't guarantee there is no problem. Asan similarly cannot catch all issues. To be clear, all these tools are very helpful, but should be used for their intended purpose and not to verify that code is correct.

However, the assertion assert(i==5) isn't triggered because of the Undefined Behaviour. The compiler doesn't even bother assert as i is just rubbish value.

The assertion isn't triggered because the program segfaults on the line that calls iter_move. Unfortunately, Godbolt output doesn't make it very clear, but 139 isn't the value of i, it's the return code of a program upon receiving sigsegv (11, which is the code of the signal, + 128).

From the perspective of the standard, the Godbolt program might be equivalently undefined compared to this patch, but in practice there is a very important difference -- the program dereferences this after the destructor has been run, while this patch doesn't.

To be clear, I would love to do it another way that doesn't require this sort of "this is technically undefined but works in practice" analysis. Unfortunately, I don't really see it. constexpr would be the perfect solution if it were not for the coverage problems. I think that tooling works best as complimentary, not the exclusive means of detecting this sort of issue.

There are some possible mitigations we could do as well. We can make sure this test runs without optimizations, we may restrict it to a certain compiler version if need be, and we could add a fail.cpp test to make sure it actually fails in practice (when encountering memory problems). I think this is overkill, personally, but wouldn't object if you feel strongly about this.

[huixie90]

In D130330#3673581, @var-const wrote:

My original test has some coverage (would fail on gcc). I am trying to figure out why clang passes the test. See this reproduction example (it is basically my original test plus making Reference destructor to set _i to be nullptr

That's exactly my experience with compiler warnings and tools like Asan -- all of them are essentially "best effort" and aren't reliable ("reliable" in the sense "guaranteed to catch 100% of issues"). In fact, when I did the first patch to fix the Chromium issue, Clang could see the dangling temporary in the original version of __iter_move (that returned a dangling value_type) but not in the version from the patch (that returned a dangling reference), even though both were equally UB and essentially the same issue. You encountered a very similar problem where GCC sees a lifetime issue while Clang doesn't. I'm sure there exist counterexamples where Clang would catch something that GCC cannot spot. The point is, these warnings aren't meant to validate that the code is correct -- while their presence almost always indicates a problem, their absence doesn't guarantee there is no problem. Asan similarly cannot catch all issues. To be clear, all these tools are very helpful, but should be used for their intended purpose and not to verify that code is correct.

However, the assertion assert(i==5) isn't triggered because of the Undefined Behaviour. The compiler doesn't even bother assert as i is just rubbish value.

The assertion isn't triggered because the program segfaults on the line that calls iter_move. Unfortunately, Godbolt output doesn't make it very clear, but 139 isn't the value of i, it's the return code of a program upon receiving sigsegv (11, which is the code of the signal, + 128).

From the perspective of the standard, the Godbolt program might be equivalently undefined compared to this patch, but in practice there is a very important difference -- the program dereferences this after the destructor has been run, while this patch doesn't.

To be clear, I would love to do it another way that doesn't require this sort of "this is technically undefined but works in practice" analysis. Unfortunately, I don't really see it. constexpr would be the perfect solution if it were not for the coverage problems. I think that tooling works best as complimentary, not the exclusive means of detecting this sort of issue.

There are some possible mitigations we could do as well. We can make sure this test runs without optimizations, we may restrict it to a certain compiler version if need be, and we could add a fail.cpp test to make sure it actually fails in practice (when encountering memory problems). I think this is overkill, personally, but wouldn't object if you feel strongly about this.

Thanks for the explanation. I don't think I have strong opinions on this. I just feel that it is a bit complicated but at the same time it also relies on UB. perhaps we could try a simpler approach, e.g. the destructor sets the ptr to nulltpr so that it can trigger segv as you explained.

[Mordante]

Thanks for working on this!

In general I'm quite happy, but I would like to add test to catch "read after move" too.

I agree the current approach technically is UB, but I don't dislike it. I've seen this approach used before for life-time tracking.

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

10

Can you add that as a comment in the test itself?

54

65

This can be noexcept since we only support C++11 and later.

526

This can be just constexpr.

552

You mean a pointer to std::any?

648

653

Do you expect test_all to grow? Otherwise it could be folded in main.

[var-const]

Address feedback.

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

65

Done. There are a few leftovers from my attempt to make it work in C++03.

552

I think using any here would prevent running this test in pre-C++17 modes, right? (good idea, though)

653

Probably -- I have at least one addition in mind (I also have a personal preference for a very simple main).

[var-const]

Rebase.

[huixie90]

LGMT

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

140

optional: it might be worth setting rhs.v_ to nullptr, which would likely cause segv in case we are trying to deference the moved-from Reference

158

is this intended? why is the assignment inside an assert. I think in general it is not a good idea to make assert have side effects, as it makes program behaves differently with different compiler flags

[var-const]

Address feedback.

[var-const]

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

158

Thanks for spotting, this was a copy-paste error.

[ldionne]

This LGTM, and we should do the same for <ranges>.

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

75

[huixie90]

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

208

Should be void as this class does not have operator->

420

[Mordante]

Thanks for adding the use after move validation!
LGTM when the CI is green.

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

552

sorry I meant std::any_of.

653

I prefer a small main too, but usually I fold these small helpers in main. But no objection against your approach.

[huixie90]

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

552

It is fine to use lambda here. it is not easy to pass std::any_of because it is

1. a function template
2. an overload set.

to solve 1, usually you need to explicit specify template arguments. &my_fun<intput1, input2>

to solve 2, you need to static_cast it to a function pointer.

combining 1 and 2 is lot of code which is not worth it.

I use BOOST_HOF_LIFT all the time to lift non-functional-friendly functions to an object that can be passed around but that require Boost.

[var-const]

Address feedback and rebase.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_proxy.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// <algorithm>
-
-#include <algorithm>
-#include <cassert>
-#include <vector>
-
-struct Cpp17ProxyIterator {
-  struct Reference {
-    int* i_;
-    Reference(int& i) : i_(&i) {}
-
-    operator int() const { return *i_; }
-
-    Reference& operator=(int i) {
-      *i_ = i;
-      return *this;
-    }
-
-    friend bool operator<(const Reference& x, const Reference& y) { return *x.i_ < *y.i_; }
-
-    friend bool operator==(const Reference& x, const Reference& y) { return *x.i_ == *y.i_; }
-
-    friend void swap(Reference x, Reference y) { std::swap(*(x.i_), *(y.i_)); }
-  };
-
-  using difference_type   = int;
-  using value_type        = int;
-  using reference         = Reference;
-  using pointer           = void*;
-  using iterator_category = std::random_access_iterator_tag;
-
-  int* ptr_;
-
-  Cpp17ProxyIterator(int* ptr) : ptr_(ptr) {}
-
-  Reference operator*() const { return Reference(*ptr_); }
-
-  Cpp17ProxyIterator& operator++() {
-    ++ptr_;
-    return *this;
-  }
-
-  Cpp17ProxyIterator operator++(int) {
-    auto tmp = *this;
-    ++*this;
-    return tmp;
-  }
-
-  friend bool operator==(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ == y.ptr_; }
-  friend bool operator!=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ != y.ptr_; }
-
-  Cpp17ProxyIterator& operator--() {
-    --ptr_;
-    return *this;
-  }
-
-  Cpp17ProxyIterator operator--(int) {
-    auto tmp = *this;
-    --*this;
-    return tmp;
-  }
-
-  Cpp17ProxyIterator& operator+=(difference_type n) {
-    ptr_ += n;
-    return *this;
-  }
-
-  Cpp17ProxyIterator& operator-=(difference_type n) {
-    ptr_ -= n;
-    return *this;
-  }
-
-  Reference operator[](difference_type i) const { return Reference(*(ptr_ + i)); }
-
-  friend bool operator<(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ < y.ptr_; }
-
-  friend bool operator>(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ > y.ptr_; }
-
-  friend bool operator<=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ <= y.ptr_; }
-
-  friend bool operator>=(const Cpp17ProxyIterator& x, const Cpp17ProxyIterator& y) { return x.ptr_ >= y.ptr_; }
-
-  friend Cpp17ProxyIterator operator+(const Cpp17ProxyIterator& x, difference_type n) {
-    return Cpp17ProxyIterator(x.ptr_ + n);
-  }
-
-  friend Cpp17ProxyIterator operator+(difference_type n, const Cpp17ProxyIterator& x) {
-    return Cpp17ProxyIterator(n + x.ptr_);
-  }
-
-  friend Cpp17ProxyIterator operator-(const Cpp17ProxyIterator& x, difference_type n) {
-    return Cpp17ProxyIterator(x.ptr_ - n);
-  }
-
-  friend difference_type operator-(Cpp17ProxyIterator x, Cpp17ProxyIterator y) {
-    return static_cast<int>(x.ptr_ - y.ptr_);
-  }
-};
-
-void test() {
-  // TODO: use a custom proxy iterator instead of (or in addition to) `vector<bool>`.
-  std::vector<bool> v(5, false);
-  v[1] = true;
-  v[3] = true;
-  std::sort(v.begin(), v.end());
-  assert(std::is_sorted(v.begin(), v.end()));
-}
-
-void testCustomProxyIterator() {
-  int a[] = {5, 1, 3, 2, 4};
-  std::sort(Cpp17ProxyIterator(a), Cpp17ProxyIterator(a + 5));
-  assert(a[0] == 1);
-  assert(a[1] == 2);
-  assert(a[2] == 3);
-  assert(a[3] == 4);
-  assert(a[4] == 5);
-}
-
-int main(int, char**) {
-  test();
-  testCustomProxyIterator();
-  return 0;
-}

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <algorithm>
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <random>
+#include <set>
+
+#include "test_macros.h"
+
+// This file contains checks for lifetime issues across all the classic algorithms. It uses two complementary
+// approaches:
+// - runtime checks using a proxy iterator that tracks the lifetime of itself and its objects to catch potential
+//   lifetime issues;
+// - `constexpr` checks using a `constexpr`-friendly proxy iterator that catch undefined behavior.
+
+// A random-access proxy iterator that tracks the lifetime of itself and its `value_type` and `reference` objects to
+// prevent potential lifetime issues in algorithms.
+//
+// This class cannot be `constexpr` because its cache is a static variable. The cache cannot be provided as
+// a constructor parameter because `LifetimeIterator` has to be default-constructible.
+class LifetimeIterator {
+  // The cache simply tracks addresses of the local variables.
+  class LifetimeCache {
+    std::set<const void*> cache_;
+
+  public:
+    bool contains(const void* ptr) const { return cache_.find(ptr) != cache_.end(); }
+
+    void insert(const void* ptr) {
+      assert(!contains(ptr));
+      cache_.insert(ptr);
+    }
+
+    void erase(const void* ptr) {
+      assert(contains(ptr));
+      cache_.erase(ptr);
+    }
+  };
+
+ public:
+  struct Value {
+    int i_;
+    bool moved_from_ = false; // Check for double moves.
+
+    Value() { lifetime_cache.insert(this); }
+    Value(int i) : i_(i) { lifetime_cache.insert(this); }
+    ~Value() { lifetime_cache.erase(this); }
+
+    Value(const Value& rhs) : i_(rhs.i_) {
+      assert(lifetime_cache.contains(&rhs));
+      lifetime_cache.insert(this);
+    }
+
+    Value(Value&& rhs) TEST_NOEXCEPT : i_(rhs.i_) {
+      assert(lifetime_cache.contains(&rhs));
+
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+
+      lifetime_cache.insert(this);
+    }
+
+    Value& operator=(const Value& rhs) {
+      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
+
+      i_ = rhs.i_;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    Value& operator=(Value&& rhs) TEST_NOEXCEPT {
+      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+
+      i_ = rhs.i_;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    friend bool operator<(const Value& x, const Value& y) {
+      assert(lifetime_cache.contains(&x) && lifetime_cache.contains(&y));
+      return x.i_ < y.i_;
+    }
+
+    friend bool operator==(const Value& x, const Value& y) {
+      assert(lifetime_cache.contains(&x) && lifetime_cache.contains(&y));
+      return x.i_ == y.i_;
+    }
+
+  };
+
+  struct Reference {
+    Value* v_;
+    bool moved_from_ = false; // Check for double moves.
+
+    Reference(Value& v) : v_(&v) {
+      lifetime_cache.insert(this);
+    }
+
+    ~Reference() {
+      lifetime_cache.erase(this);
+    }
+
+    Reference(const Reference& rhs) : v_(rhs.v_) {
+      assert(lifetime_cache.contains(&rhs));
+      lifetime_cache.insert(this);
+    }
+
+    Reference(Reference&& rhs) TEST_NOEXCEPT : v_(rhs.v_) {
+      assert(lifetime_cache.contains(&rhs));
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+
+      lifetime_cache.insert(this);
+    }
+
+    Reference& operator=(const Reference& rhs) {
+      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
+
+      v_ = rhs.v_;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    Reference& operator=(Reference&& rhs) TEST_NOEXCEPT {
+      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+
+      v_ = rhs.v_;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    operator Value() const {
+      assert(lifetime_cache.contains(this));
+      return *v_;
+    }
+
+    Reference& operator=(Value v) {
+      assert(lifetime_cache.contains(this));
+
+      *v_ = v;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    friend bool operator<(const Reference& lhs, const Reference& rhs) {
+      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
+      return *lhs.v_ < *rhs.v_;
+    }
+
+    friend bool operator==(const Reference& lhs, const Reference& rhs) {
+      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
+      return *lhs.v_ == *rhs.v_;
+    }
+
+    friend void swap(Reference lhs, Reference rhs) {
+      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
+      std::swap(*(lhs.v_), *(rhs.v_));
+    }
+  };
+
+  using difference_type   = int;
+  using value_type        = Value;
+  using reference         = Reference;
+  using pointer           = void*;
+  using iterator_category = std::random_access_iterator_tag;
+
+  Value* ptr_ = nullptr;
+  bool moved_from_ = false; // Check for double moves.
+
+  LifetimeIterator() = default;
+  LifetimeIterator(Value* ptr) : ptr_(ptr) {}
+
+  LifetimeIterator(const LifetimeIterator&) = default;
+
+  LifetimeIterator& operator=(const LifetimeIterator& rhs) {
+    ptr_ = rhs.ptr_;
+    moved_from_ = false;
+
+    return *this;
+  }
+
+  LifetimeIterator(LifetimeIterator&& rhs) TEST_NOEXCEPT : ptr_(rhs.ptr_) {
+    assert(!rhs.moved_from_);
+    rhs.moved_from_ = true;
+  }
+
+  LifetimeIterator& operator=(LifetimeIterator&& rhs) TEST_NOEXCEPT {
+    assert(!rhs.moved_from_);
+    rhs.moved_from_ = true;
+    moved_from_ = false;
+
+    ptr_ = rhs.ptr_;
+
+    return *this;
+  }
+
+  Reference operator*() const { return Reference(*ptr_); }
+
+  LifetimeIterator& operator++() {
+    ++ptr_;
+    return *this;
+  }
+
+  LifetimeIterator operator++(int) {
+    auto tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  friend bool operator==(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ == y.ptr_; }
+  friend bool operator!=(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ != y.ptr_; }
+
+  LifetimeIterator& operator--() {
+    --ptr_;
+    return *this;
+  }
+
+  LifetimeIterator operator--(int) {
+    auto tmp = *this;
+    --*this;
+    return tmp;
+  }
+
+  LifetimeIterator& operator+=(difference_type n) {
+    ptr_ += n;
+    return *this;
+  }
+
+  LifetimeIterator& operator-=(difference_type n) {
+    ptr_ -= n;
+    return *this;
+  }
+
+  Reference operator[](difference_type i) const { return Reference(*(ptr_ + i)); }
+
+  friend bool operator<(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ < y.ptr_; }
+
+  friend bool operator>(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ > y.ptr_; }
+
+  friend bool operator<=(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ <= y.ptr_; }
+
+  friend bool operator>=(const LifetimeIterator& x, const LifetimeIterator& y) { return x.ptr_ >= y.ptr_; }
+
+  friend LifetimeIterator operator+(const LifetimeIterator& x, difference_type n) {
+    return LifetimeIterator(x.ptr_ + n);
+  }
+
+  friend LifetimeIterator operator+(difference_type n, const LifetimeIterator& x) {
+    return LifetimeIterator(n + x.ptr_);
+  }
+
+  friend LifetimeIterator operator-(const LifetimeIterator& x, difference_type n) {
+    return LifetimeIterator(x.ptr_ - n);
+  }
+
+  friend difference_type operator-(LifetimeIterator x, LifetimeIterator y) {
+    return static_cast<int>(x.ptr_ - y.ptr_);
+  }
+
+  static LifetimeCache lifetime_cache;
+};
+
+LifetimeIterator::LifetimeCache LifetimeIterator::lifetime_cache;
+
+#if TEST_STD_VER > 17
+// A constexpr-friendly proxy iterator to check for undefined behavior in algorithms (since undefined behavior is
+// statically caught in `constexpr` context).
+class ConstexprIterator {
+ public:
+  struct Reference {
+    int* v_;
+    bool moved_from_ = false; // Check for double moves.
+
+    constexpr Reference(int& v) : v_(&v) { }
+
+    constexpr Reference(const Reference& rhs) = default;
+    constexpr Reference& operator=(const Reference& rhs) {
+      v_ = rhs.v_;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    constexpr Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+    }
+
+    constexpr Reference& operator=(Reference&& rhs) noexcept {
+      assert(!rhs.moved_from_);
+      assert(rhs.moved_from_ = true);
+      moved_from_ = false;
+
+      v_ = rhs.v_;
+      return *this;
+    }
+
+    constexpr operator int() const { return *v_; }
+
+    constexpr Reference& operator=(int v) {
+      *v_ = v;
+      moved_from_ = false;
+
+      return *this;
+    }
+
+    friend constexpr bool operator<(const Reference& x, const Reference& y) { return *x.v_ < *y.v_; }
+
+    friend constexpr bool operator==(const Reference& x, const Reference& y) { return *x.v_ == *y.v_; }
+
+    friend constexpr void swap(Reference x, Reference y) { std::swap(*(x.v_), *(y.v_)); }
+  };
+
+  using difference_type   = int;
+  using value_type        = int;
+  using reference         = Reference;
+  using pointer           = void*;
+  using iterator_category = std::random_access_iterator_tag;
+
+  int* ptr_ = nullptr;
+  bool moved_from_ = false; // Check for double moves.
+
+  constexpr ConstexprIterator() = default;
+  constexpr ConstexprIterator(int* ptr) : ptr_(ptr) {}
+
+  constexpr ConstexprIterator(const ConstexprIterator& rhs) = default;
+
+  constexpr ConstexprIterator& operator=(const ConstexprIterator& rhs) {
+    ptr_ = rhs.ptr_;
+    moved_from_ = false;
+
+    return *this;
+  }
+
+  constexpr ConstexprIterator(ConstexprIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
+    assert(!rhs.moved_from_);
+    assert(rhs.moved_from_ = true);
+  }
+
+  constexpr ConstexprIterator& operator=(ConstexprIterator&& rhs) noexcept {
+    assert(!rhs.moved_from_);
+    assert(rhs.moved_from_ = true);
+    moved_from_ = false;
+
+    ptr_ = rhs.ptr_;
+    return *this;
+  }
+
+  constexpr Reference operator*() const { return Reference(*ptr_); }
+
+  constexpr ConstexprIterator& operator++() {
+    ++ptr_;
+    return *this;
+  }
+
+  constexpr ConstexprIterator operator++(int) {
+    auto tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  friend constexpr bool operator==(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ == y.ptr_; }
+  friend constexpr bool operator!=(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ != y.ptr_; }
+
+  constexpr ConstexprIterator& operator--() {
+    --ptr_;
+    return *this;
+  }
+
+  constexpr ConstexprIterator operator--(int) {
+    auto tmp = *this;
+    --*this;
+    return tmp;
+  }
+
+  constexpr ConstexprIterator& operator+=(difference_type n) {
+    ptr_ += n;
+    return *this;
+  }
+
+  constexpr ConstexprIterator& operator-=(difference_type n) {
+    ptr_ -= n;
+    return *this;
+  }
+
+  constexpr Reference operator[](difference_type i) const { return Reference(*(ptr_ + i)); }
+
+  friend constexpr bool operator<(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ < y.ptr_; }
+
+  friend constexpr bool operator>(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ > y.ptr_; }
+
+  friend constexpr bool operator<=(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ <= y.ptr_; }
+
+  friend constexpr bool operator>=(const ConstexprIterator& x, const ConstexprIterator& y) { return x.ptr_ >= y.ptr_; }
+
+  friend constexpr ConstexprIterator operator+(const ConstexprIterator& x, difference_type n) {
+    return ConstexprIterator(x.ptr_ + n);
+  }
+
+  friend constexpr ConstexprIterator operator+(difference_type n, const ConstexprIterator& x) {
+    return ConstexprIterator(n + x.ptr_);
+  }
+
+  friend constexpr ConstexprIterator operator-(const ConstexprIterator& x, difference_type n) {
+    return ConstexprIterator(x.ptr_ - n);
+  }
+
+  friend constexpr difference_type operator-(ConstexprIterator x, ConstexprIterator y) {
+    return static_cast<int>(x.ptr_ - y.ptr_);
+  }
+};
+
+#endif // TEST_STD_VER > 17
+
+template <class T, size_t N = 32>
+class Input {
+  using Array = std::array<T, N>;
+
+  size_t size_ = 0;
+  Array values_ = {};
+
+public:
+  template <size_t N2>
+  TEST_CONSTEXPR_CXX20 Input(std::array<T, N2> from) {
+    static_assert(N2 <= N, "Input is too large");
+
+    std::copy(from.begin(), from.end(), begin());
+    size_ = N2;
+  }
+
+  TEST_CONSTEXPR_CXX20 typename Array::iterator begin() { return values_.begin(); }
+  TEST_CONSTEXPR_CXX20 typename Array::iterator end() { return values_.begin() + size_; }
+  TEST_CONSTEXPR_CXX20 size_t size() const { return size_; }
+};
+
+// TODO: extend `Value` and `Reference` so that it's possible to pass plain integers to all the algorithms.
+
+// Several generic inputs that are useful for many algorithms. Provides two unsorted sequences with and without
+// duplicates, with positive and negative values; and a few corner cases, like an empty sequence, a sequence of all
+// duplicates, and so on.
+template <class Iter>
+TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_simple_in() {
+  using T = typename Iter::value_type;
+  std::array<Input<T>, 8> result = {
+    Input<T>({std::array<T, 0>{ }}),
+    Input<T>({std::array<T, 1>{ T{1} }}),
+    Input<T>({std::array<T, 1>{ T{-1} }}),
+    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
+    Input<T>({std::array<T, 9>{ T{-8}, {6}, {3}, {2}, {1}, {5}, {-4}, {-9}, {3} }}),
+    Input<T>({std::array<T, 9>{ T{-8}, {3}, {3}, {2}, {5}, {-4}, {-4}, {-4}, {1} }}),
+  };
+  return result;
+}
+
+// Sorted inputs of varying lengths.
+template <class Iter>
+TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sorted_in() {
+  using T = typename Iter::value_type;
+  std::array<Input<T>, 8> result = {
+    Input<T>({std::array<T, 0>{ }}),
+    Input<T>({std::array<T, 1>{ T{1} }}),
+    Input<T>({std::array<T, 1>{ T{-1} }}),
+    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
+    Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
+    Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
+  };
+  return result;
+}
+
+// Inputs for testing `std::sort`. These have been manually verified to exercise all internal functions in `std::sort`
+// except the branchless sort ones (which can't be triggered with proxy arrays).
+template <class Iter>
+TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sort_test_in() {
+  using T = typename Iter::value_type;
+  std::array<Input<T>, 8> result = {
+    Input<T>({std::array<T, 0>{ }}),
+    Input<T>({std::array<T, 1>{ T{1} }}),
+    Input<T>({std::array<T, 1>{ T{-1} }}),
+    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
+    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
+    Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
+    Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
+  };
+  return result;
+}
+
+template <class Input, size_t N, class Func>
+TEST_CONSTEXPR_CXX20 void test(std::array<Input, N> inputs, Func func) {
+  for (auto&& in : inputs) {
+    func(in.begin(), in.end());
+  }
+}
+
+template <class Input, size_t N, class Func>
+TEST_CONSTEXPR_CXX20 void test_n(std::array<Input, N> inputs, Func func) {
+  for (auto&& in : inputs) {
+    func(in.begin(), in.size());
+  }
+}
+
+TEST_CONSTEXPR int to_int(int x) { return x; }
+int to_int(LifetimeIterator::Value x) { return x.i_; }
+
+std::mt19937 rand_gen() { return std::mt19937(); }
+
+template <class Iter>
+TEST_CONSTEXPR_CXX20 bool test() {
+  using T = typename Iter::value_type;
+
+  auto is_neg = [](const T& val) { return to_int(val) < 0; };
+  auto gen = [] { return T{42}; };
+  auto identity = [] (T val) -> T { return val; };
+
+  TEST_CONSTEXPR int N = 32;
+  std::array<T, N> output;
+  auto out = output.begin();
+  T x{1};
+  T y{3};
+
+  auto simple_in = get_simple_in<Iter>();
+  auto sorted_in = get_sorted_in<Iter>();
+  auto sort_test_in = get_sort_test_in<Iter>();
+
+  using I = Iter;
+
+  test(simple_in, [&](I b, I e) { std::any_of(b, e, is_neg); });
+  test(simple_in, [&](I b, I e) { std::all_of(b, e, is_neg); });
+  test(simple_in, [&](I b, I e) { std::none_of(b, e, is_neg); });
+  test(simple_in, [&](I b, I e) { std::find(b, e, T{1}); });
+  test(simple_in, [&](I b, I e) { std::find_if(b, e, is_neg); });
+  test(simple_in, [&](I b, I e) { std::find_if_not(b, e, is_neg); });
+  // TODO: find_first_of
+  test(simple_in, [&](I b, I e) { std::adjacent_find(b, e); });
+  // TODO: mismatch
+  // TODO: equal
+  // TODO: lexicographical_compare
+  // TODO: partition_point
+  test(sorted_in, [&](I b, I e) { std::lower_bound(b, e, x); });
+  test(sorted_in, [&](I b, I e) { std::upper_bound(b, e, x); });
+  test(sorted_in, [&](I b, I e) { std::equal_range(b, e, x); });
+  test(sorted_in, [&](I b, I e) { std::binary_search(b, e, x); });
+  // `min`, `max` and `minmax` don't use iterators.
+  test(simple_in, [&](I b, I e) { std::min_element(b, e); });
+  test(simple_in, [&](I b, I e) { std::max_element(b, e); });
+  test(simple_in, [&](I b, I e) { std::minmax_element(b, e); });
+  test(simple_in, [&](I b, I e) { std::count(b, e, x); });
+  test(simple_in, [&](I b, I e) { std::count_if(b, e, is_neg); });
+  // TODO: search
+  // TODO: search_n
+  // TODO: find_end
+  // TODO: is_partitioned
+  // TODO: is_sorted
+  // TODO: is_sorted_until
+  // TODO: includes
+  // TODO: is_heap
+  // TODO: is_heap_until
+  // `clamp` doesn't use iterators.
+  // TODO: is_permutation
+  test(simple_in, [&](I b, I e) { std::for_each(b, e, is_neg); });
+#if TEST_STD_VER > 14
+  test_n(simple_in, [&](I b, size_t n) { std::for_each_n(b, n, is_neg); });
+#endif
+  test(simple_in, [&](I b, I e) { std::copy(b, e, out); });
+  test_n(simple_in, [&](I b, size_t n) { std::copy_n(b, n, out); });
+  test(simple_in, [&](I b, I e) { std::copy_backward(b, e, out + N); });
+  test(simple_in, [&](I b, I e) { std::copy_if(b, e, out, is_neg); });
+  test(simple_in, [&](I b, I e) { std::move(b, e, out); });
+  test(simple_in, [&](I b, I e) { std::move_backward(b, e, out + N); });
+  test(simple_in, [&](I b, I e) { std::transform(b, e, out, identity); });
+  test(simple_in, [&](I b, I e) { std::generate(b, e, gen); });
+  test_n(simple_in, [&](I b, size_t n) { std::generate_n(b, n, gen); });
+  test(simple_in, [&](I b, I e) { std::remove_copy(b, e, out, x); });
+  test(simple_in, [&](I b, I e) { std::remove_copy_if(b, e, out, is_neg); });
+  test(simple_in, [&](I b, I e) { std::replace(b, e, x, y); });
+  test(simple_in, [&](I b, I e) { std::replace_if(b, e, is_neg, y); });
+  test(simple_in, [&](I b, I e) { std::replace_copy(b, e, out, x, y); });
+  test(simple_in, [&](I b, I e) { std::replace_copy_if(b, e, out, is_neg, y); });
+  // TODO: swap_ranges
+  test(simple_in, [&](I b, I e) { std::reverse_copy(b, e, out); });
+  // TODO: rotate_copy
+  // TODO: sample
+  // TODO: unique_copy
+  // TODO: partition_copy
+  // TODO: partial_sort_copy
+  // TODO: merge
+  // TODO: set_difference
+  // TODO: set_intersection
+  // TODO: set_symmetric_difference
+  // TODO: set_union
+  test(simple_in, [&](I b, I e) { std::remove(b, e, x); });
+  test(simple_in, [&](I b, I e) { std::remove_if(b, e, is_neg); });
+  test(simple_in, [&](I b, I e) { std::reverse(b, e); });
+  // TODO: rotate
+  if (!TEST_IS_CONSTANT_EVALUATED)
+    test(simple_in, [&](I b, I e) { std::shuffle(b, e, rand_gen()); });
+  // TODO: unique
+  test(simple_in, [&](I b, I e) { std::partition(b, e, is_neg); });
+  if (!TEST_IS_CONSTANT_EVALUATED)
+    test(simple_in, [&](I b, I e) { std::stable_partition(b, e, is_neg); });
+  if (!TEST_IS_CONSTANT_EVALUATED)
+    test(sort_test_in, [&](I b, I e) { std::sort(b, e); });
+  if (!TEST_IS_CONSTANT_EVALUATED)
+    test(sort_test_in, [&](I b, I e) { std::stable_sort(b, e); });
+  // TODO: partial_sort
+  // TODO: nth_element
+  // TODO: inplace_merge
+  test(simple_in, [&](I b, I e) { std::make_heap(b, e); });
+  // TODO: push_heap
+  // TODO: pop_heap
+  // TODO: sort_heap
+  test(simple_in, [&](I b, I e) { std::prev_permutation(b, e); });
+  test(simple_in, [&](I b, I e) { std::next_permutation(b, e); });
+
+  // TODO: algorithms in `<numeric>`
+  // TODO: algorithms in `<memory>`
+
+  return true;
+}
+
+void test_all() {
+  test<LifetimeIterator>();
+#if TEST_STD_VER > 17 // Most algorithms are only `constexpr` starting from C++20.
+  static_assert(test<ConstexprIterator>(), "");
+#endif
+}
+
+int main(int, char**) {
+  test_all();
+
+  return 0;
+}