[PATCH][Bug libstdc++/70303] Value-initialized debug iterators

[Jonathan Wakely]

On 31/01/21 16:59 +0100, François Dumont via Libstdc++ wrote:
>After the debug issue has been fixed in PR 98466 the problem was not 
>in the debug iterator implementation itself but in the deque iterator 
>operator- implementation.
>
>    libstdc++: Make deque iterator operator- usable with value-init 
>iterators
>
>    N3644 implies that operator- can be used on value-init iterators. 
>We now return
>    0 if both iterators are value initialized. If only one is value 
>initialized we
>    keep the UB by returning the result of a normal computation which 
>is an unexpected
>    value.
>
>    libstdc++/ChangeLog:
>
>            PR libstdc++/70303
>            * include/bits/stl_deque.h 
>(std::deque<>::operator-(iterator, iterator)):
>            Return 0 if both iterators are value-initialized.
>            * testsuite/23_containers/deque/70303.cc: New test.
>            * testsuite/23_containers/vector/70303.cc: New test.
>
>Tested under Linux x86_64, ok to commit ?

OK.

I don't like adding the branch there though. Even with the
__builtin_expect it causes worse code to be generated than the
original.

This would be branchless, but a bit harder to understand:

     return difference_type(__x._S_buffer_size())
       * (__x._M_node - __y._M_node - int(__x._M_node == __y._M_node))
       + (__x._M_cur - __x._M_first) + (__y._M_last - __y._M_cur);

Please commit the fix and we can think about it later.

>François
>

>diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
>index d41c27717a3..04b70b77621 100644
>--- a/libstdc++-v3/include/bits/stl_deque.h
>+++ b/libstdc++-v3/include/bits/stl_deque.h
>@@ -352,9 +352,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       friend difference_type
>       operator-(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
>       {
>-	return difference_type(_S_buffer_size())
>-	  * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
>-	  + (__y._M_last - __y._M_cur);
>+	if (__builtin_expect(__x._M_node || __y._M_node, true))
>+	  return difference_type(_S_buffer_size())
>+	    * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
>+	    + (__y._M_last - __y._M_cur);
>+
>+	return 0;
>       }
> 
>       // _GLIBCXX_RESOLVE_LIB_DEFECTS
>@@ -366,9 +369,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	operator-(const _Self& __x,
> 		  const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
> 	{
>-	  return difference_type(_S_buffer_size())
>-	    * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
>-	    + (__y._M_last - __y._M_cur);
>+	  if (__builtin_expect(__x._M_node || __y._M_node, true))
>+	    return difference_type(_S_buffer_size())
>+	      * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
>+	      + (__y._M_last - __y._M_cur);
>+
>+	  return 0;
> 	}
> 
>       friend _Self
>diff --git a/libstdc++-v3/testsuite/23_containers/deque/70303.cc b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
>new file mode 100644
>index 00000000000..e0e63694170
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/deque/70303.cc
>@@ -0,0 +1,67 @@
>+// Copyright (C) 2021 Free Software Foundation, Inc.
>+//
>+// This file is part of the GNU ISO C++ Library.  This library is free
>+// software; you can redistribute it and/or modify it under the
>+// terms of the GNU General Public License as published by the
>+// Free Software Foundation; either version 3, or (at your option)
>+// any later version.
>+
>+// This library is distributed in the hope that it will be useful,
>+// but WITHOUT ANY WARRANTY; without even the implied warranty of
>+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>+// GNU General Public License for more details.
>+
>+// You should have received a copy of the GNU General Public License along
>+// with this library; see the file COPYING3.  If not see
>+// <http://www.gnu.org/licenses/>.
>+
>+// { dg-do run }
>+
>+#include <deque>
>+#include <testsuite_hooks.h>
>+
>+// PR libstdc++/70303
>+
>+void test01()
>+{
>+  typedef typename std::deque<int>::iterator It;
>+  It it = It();
>+  VERIFY(it == it);
>+  VERIFY(!(it != it));
>+  VERIFY(it - it == 0);
>+  VERIFY(!(it < it));
>+  VERIFY(!(it > it));
>+  VERIFY(it <= it);
>+  VERIFY(it >= it);
>+
>+  typedef typename std::deque<int>::const_iterator CIt;
>+  CIt cit = CIt();
>+  VERIFY(cit == cit);
>+  VERIFY(!(cit != cit));
>+  VERIFY(cit - cit == 0);
>+  VERIFY(!(cit < cit));
>+  VERIFY(!(cit > cit));
>+  VERIFY(cit <= cit);
>+  VERIFY(cit >= cit);
>+
>+  VERIFY(it == cit);
>+  VERIFY(!(it != cit));
>+  VERIFY(cit == it);
>+  VERIFY(!(cit != it));
>+  VERIFY(it - cit == 0);
>+  VERIFY(cit - it == 0);
>+  VERIFY(!(it < cit));
>+  VERIFY(!(it > cit));
>+  VERIFY(it <= cit);
>+  VERIFY(it >= cit);
>+  VERIFY(!(cit < it));
>+  VERIFY(!(cit > it));
>+  VERIFY(cit <= it);
>+  VERIFY(cit >= it);
>+}
>+
>+int main()
>+{
>+  test01();
>+  return 0;
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/vector/70303.cc b/libstdc++-v3/testsuite/23_containers/vector/70303.cc
>new file mode 100644
>index 00000000000..af18a0503d8
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/vector/70303.cc
>@@ -0,0 +1,67 @@
>+// Copyright (C) 2021 Free Software Foundation, Inc.
>+//
>+// This file is part of the GNU ISO C++ Library.  This library is free
>+// software; you can redistribute it and/or modify it under the
>+// terms of the GNU General Public License as published by the
>+// Free Software Foundation; either version 3, or (at your option)
>+// any later version.
>+
>+// This library is distributed in the hope that it will be useful,
>+// but WITHOUT ANY WARRANTY; without even the implied warranty of
>+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>+// GNU General Public License for more details.
>+
>+// You should have received a copy of the GNU General Public License along
>+// with this library; see the file COPYING3.  If not see
>+// <http://www.gnu.org/licenses/>.
>+
>+// { dg-do run }
>+
>+#include <vector>
>+#include <testsuite_hooks.h>
>+
>+// PR libstdc++/70303
>+
>+void test01()
>+{
>+  typedef typename std::vector<int>::iterator It;
>+  It it = It();
>+  VERIFY(it == it);
>+  VERIFY(!(it != it));
>+  VERIFY(it - it == 0);
>+  VERIFY(!(it < it));
>+  VERIFY(!(it > it));
>+  VERIFY(it <= it);
>+  VERIFY(it >= it);
>+
>+  typedef typename std::vector<int>::const_iterator CIt;
>+  CIt cit = CIt();
>+  VERIFY(cit == cit);
>+  VERIFY(!(cit != cit));
>+  VERIFY(cit - cit == 0);
>+  VERIFY(!(cit < cit));
>+  VERIFY(!(cit > cit));
>+  VERIFY(cit <= cit);
>+  VERIFY(cit >= cit);
>+
>+  VERIFY(it == cit);
>+  VERIFY(!(it != cit));
>+  VERIFY(cit == it);
>+  VERIFY(!(cit != it));
>+  VERIFY(it - cit == 0);
>+  VERIFY(cit - it == 0);
>+  VERIFY(!(it < cit));
>+  VERIFY(!(it > cit));
>+  VERIFY(it <= cit);
>+  VERIFY(it >= cit);
>+  VERIFY(!(cit < it));
>+  VERIFY(!(cit > it));
>+  VERIFY(cit <= it);
>+  VERIFY(cit >= it);
>+}
>+
>+int main()
>+{
>+  test01();
>+  return 0;
>+}