Fix PR#23767. Add tests for iterator invalidation for deque::erase/pop_front/pop_back

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@239196 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 248 insertions, 2 deletions

diff --git a/include/deque b/include/deque
index 78ef118c3..a372560f6 100644
--- a/include/deque
+++ b/include/deque
@@ -2699,7 +2699,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f)
     difference_type __pos = __f - __b;
     iterator __p = __b + __pos;
     allocator_type& __a = __base::__alloc();
-    if (__pos < (__base::size() - 1) / 2)
+    if (__pos <= (__base::size() - 1) / 2)
     {   // erase from front
         _VSTD::move_backward(__b, __p, _VSTD::next(__p));
         __alloc_traits::destroy(__a, _VSTD::addressof(*__b));
@@ -2737,7 +2737,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l)
     if (__n > 0)
     {
         allocator_type& __a = __base::__alloc();
-        if (__pos < (__base::size() - __n) / 2)
+        if (__pos <= (__base::size() - __n) / 2)
         {   // erase from front
             iterator __i = _VSTD::move_backward(__b, __p, __p + __n);
             for (; __b != __i; ++__b)
diff --git a/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp b/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp
new file mode 100644
index 000000000..49465cdda
--- /dev/null
+++ b/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp
@@ -0,0 +1,70 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// iterator erase(const_iterator f)
+
+//  Erasing items from the beginning or the end of a deque shall not invalidate iterators
+//  to items that were not erased.
+
+#include <deque>
+#include <cassert>
+
+template <typename C>
+void del_at_start(C c)
+{
+    typename C::iterator first = c.begin();
+    typename C::iterator it1 = first + 1;
+    typename C::iterator it2 = c.end() - 1;
+    
+    c.erase (first);
+    
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+
+template <typename C>
+void del_at_end(C c)
+{
+    typename C::iterator first = c.end() - 1;
+    typename C::iterator it1 = c.begin();
+    typename C::iterator it2 = first - 1;
+    
+    c.erase (first);
+
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+
+int main()
+{
+    std::deque<int> queue;
+    for (int i = 0; i < 20; ++i)
+        queue.push_back(i);
+    
+    while (queue.size() > 1)
+    {
+        del_at_start(queue);
+        del_at_end(queue);
+        queue.pop_back();
+    }
+}
diff --git a/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp b/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp
new file mode 100644
index 000000000..c785e264d
--- /dev/null
+++ b/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp
@@ -0,0 +1,78 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// iterator erase(const_iterator f, const_iterator l)
+
+//  Erasing items from the beginning or the end of a deque shall not invalidate iterators
+//  to items that were not erased.
+
+
+#include <deque>
+#include <cstdint>
+#include <cassert>
+
+template <typename C>
+void del_at_start(C c, size_t num)
+{
+    typename C::iterator first = c.begin();
+    typename C::iterator last  = first + num;
+    typename C::iterator it1 = last;
+    typename C::iterator it2 = c.end() - 1;
+    
+    c.erase (first, last);
+    
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+    
+template <typename C>
+void del_at_end(C c, size_t num)
+{
+    typename C::iterator last  = c.end();
+    typename C::iterator first = last - num;
+    typename C::iterator it1 = c.begin();
+    typename C::iterator it2 = first - 1;
+    
+    c.erase (first, last);
+
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+
+
+int main()
+{
+    std::deque<int> queue;
+    for (int i = 0; i < 20; ++i)
+        queue.push_back(i);
+
+    while (queue.size() > 1)
+    {
+        for (size_t i = 1; i < queue.size(); ++i)
+        {
+            del_at_start(queue, i);
+            del_at_end  (queue, i);
+        }
+        queue.pop_back();
+    }
+}
diff --git a/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp b/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp
new file mode 100644
index 000000000..1d84f73cc
--- /dev/null
+++ b/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp
@@ -0,0 +1,49 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// void pop_back()
+
+//  Erasing items from the beginning or the end of a deque shall not invalidate iterators
+//  to items that were not erased.
+
+#include <deque>
+#include <cassert>
+
+template <typename C>
+void test(C c)
+{
+    typename C::iterator it1 = c.begin();
+    typename C::iterator it2 = c.end() - 2;
+    
+    c.pop_back();
+    
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+
+int main()
+{
+    std::deque<int> queue;
+    for (int i = 0; i < 20; ++i)
+        queue.push_back(i);
+    
+    while (queue.size() > 1)
+    {
+        test(queue);
+        queue.pop_back();
+    }
+}
diff --git a/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp b/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp
new file mode 100644
index 000000000..78317f3a3
--- /dev/null
+++ b/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp
@@ -0,0 +1,49 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// void pop_front()
+
+//  Erasing items from the beginning or the end of a deque shall not invalidate iterators
+//  to items that were not erased.
+
+#include <deque>
+#include <cassert>
+
+template <typename C>
+void test(C c)
+{
+    typename C::iterator it1 = c.begin() + 1;
+    typename C::iterator it2 = c.end() - 1;
+    
+    c.pop_front();
+    
+    typename C::iterator it3 = c.begin();
+    typename C::iterator it4 = c.end() - 1;
+    assert(  it1 ==   it3);
+    assert( *it1 ==  *it3);
+    assert(&*it1 == &*it3);
+    assert(  it2 ==   it4);
+    assert( *it2 ==  *it4);
+    assert(&*it2 == &*it4);
+}
+
+int main()
+{
+    std::deque<int> queue;
+    for (int i = 0; i < 20; ++i)
+        queue.push_back(i);
+    
+    while (queue.size() > 1)
+    {
+        test(queue);
+        queue.pop_back();
+    }
+}