Re: vector lightweight debug mode

[FranÃois Dumont <frs dot dumont at gmail dot com>]

On 07/10/2015 22:09, Jonathan Wakely wrote:
> On 07/10/15 21:38 +0200, François Dumont wrote:
>> Hi
>>
>>    I completed vector assertion mode. Here is the result of the new
>> test you will find in the attached patch.
>>
>> With debug mode:
>> /home/fdt/dev/gcc/build_git/x86_64-unknown-linux-gnu/libstdc++-v3/include/debug/safe_iterator.h:375:
>>
>> Error: attempt to advance a dereferenceable (start-of-sequence)
>> iterator 2
>> steps, which falls outside its valid range.
>>
>> Objects involved in the operation:
>>    iterator @ 0x0x7fff1c346760 {
>>      type =
>> __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*,
>> std::__cxx1998::vector<int, std::allocator<int> > >,
>> std::__debug::vector<int, std::allocator<int> > > (mutable iterator);
>>      state = dereferenceable (start-of-sequence);
>>      references sequence with type 'std::__debug::vector<int,
>> std::allocator<int> >' @ 0x0x7fff1c3469a0
>>    }
>> XFAIL: 23_containers/vector/debug/insert8_neg.cc execution test
>>
>>
>> With assertion mode:
>> /home/fdt/dev/gcc/build_git/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/stl_vector.h:1124:
>>
>> Error: invalid insert position outside container [begin, end) range.
>>
>> Objects involved in the operation:
>>    sequence "this" @ 0x0x7fff60b1f870 {
>>      type = std::vector<int, std::allocator<int> >;
>>    }
>>    iterator "__position" @ 0x0x7fff60b1f860 {
>>      type = __gnu_cxx::__normal_iterator<int const*, std::vector<int,
>> std::allocator<int> > >;
>>    }
>> XFAIL: 23_containers/vector/debug/insert8_neg.cc execution test
>
> I still don't like the formatted output for the lightweight mode, it
> adds a dependency on I/O support in libc, which is a problem for
> embedded systems.

I thought you just meant I/O dependency in terms of included headers.
The __glibcxx_assert also has some I/O as in case of failure it calls:

  inline void
  __replacement_assert(const char* __file, int __line,
               const char* __function, const char* __condition)
  {
    __builtin_printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
             __function, __condition);
    __builtin_abort();
  }

but it is much more limited than the _GLIBCXX_DEBUG_VERIFY counterpart
which is calling fprintf to send to stderr.

So ok let's limit this mode to glibcxx_assert.

>
> The idea was to just add really cheap checks and abort  :-(
>
> Have you compared codegen with and without assertion mode? How much
> more code is added to member functions like operator[] that must be
> inlined for good performance?  Is it likely to affect inlining
> decisions?
>
> I suspect it will have a much bigger impact than if we just use
> __builtin_abort() as I made it do originally.

I think that impact on compiled code depends more on the assert
condition than on the code executed when this assertion happens to be
false. But I haven't check it and will try.

In the attached patch I eventually:
- Move assertion macros in debug/assertions.h, it sounds like the right
place for those.
- Complete implementation of assertion checks by using __valid_range
function. All checks I can think of are now in place. I still need to
compare with google branch.

Note that for the latter, condition is still evaluated in O(1).
__valid_range detects iterator issues without looping through them.
__valid_range, by considering iterator category, also make those macros
usable in any container.

François

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 305d446..04bc339 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -63,6 +63,8 @@
 #include <initializer_list>
 #endif
 
+#include <debug/assertions.h>
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -403,13 +405,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         vector(_InputIterator __first, _InputIterator __last,
 	       const allocator_type& __a = allocator_type())
 	: _Base(__a)
-        { _M_initialize_dispatch(__first, __last, __false_type()); }
+        {
+	  __glibcxx_requires_valid_range(__first, __last);
+	  _M_initialize_dispatch(__first, __last, __false_type());
+	}
 #else
       template<typename _InputIterator>
         vector(_InputIterator __first, _InputIterator __last,
 	       const allocator_type& __a = allocator_type())
 	: _Base(__a)
         {
+	  __glibcxx_requires_valid_range(__first, __last);
+
 	  // Check whether it's an integral type.  If so, it's not an iterator.
 	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 	  _M_initialize_dispatch(__first, __last, _Integral());
@@ -470,7 +477,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       vector&
       operator=(initializer_list<value_type> __l)
       {
-	this->assign(__l.begin(), __l.end());
+	this->_M_assign_aux(__l.begin(), __l.end(),
+			    random_access_iterator_tag());
 	return *this;
       }
 #endif
@@ -506,12 +514,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       typename = std::_RequireInputIter<_InputIterator>>
         void
         assign(_InputIterator __first, _InputIterator __last)
-        { _M_assign_dispatch(__first, __last, __false_type()); }
+        {
+	  __glibcxx_requires_valid_range(__first, __last);
+	  _M_assign_dispatch(__first, __last, __false_type());
+	}
 #else
       template<typename _InputIterator>
         void
         assign(_InputIterator __first, _InputIterator __last)
         {
+	  __glibcxx_requires_valid_range(__first, __last);
+
 	  // Check whether it's an integral type.  If so, it's not an iterator.
 	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 	  _M_assign_dispatch(__first, __last, _Integral());
@@ -532,7 +545,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       assign(initializer_list<value_type> __l)
-      { this->assign(__l.begin(), __l.end()); }
+      {
+	this->_M_assign_aux(__l.begin(), __l.end(),
+			    random_access_iterator_tag());
+      }
 #endif
 
       /// Get a copy of the memory allocation object.
@@ -778,7 +794,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       reference
       operator[](size_type __n) _GLIBCXX_NOEXCEPT
-      { return *(this->_M_impl._M_start + __n); }
+      {
+	__glibcxx_requires_subscript(__n);
+	return *(this->_M_impl._M_start + __n);
+      }
 
       /**
        *  @brief  Subscript access to the data contained in the %vector.
@@ -793,7 +812,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_reference
       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
-      { return *(this->_M_impl._M_start + __n); }
+      {
+	__glibcxx_requires_subscript(__n);
+	return *(this->_M_impl._M_start + __n);
+      }
 
     protected:
       /// Safety check used only from at().
@@ -850,7 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       reference
       front() _GLIBCXX_NOEXCEPT
-      { return *begin(); }
+      {
+	__glibcxx_requires_nonempty();
+	return *begin();
+      }
 
       /**
        *  Returns a read-only (constant) reference to the data at the first
@@ -858,7 +883,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_reference
       front() const _GLIBCXX_NOEXCEPT
-      { return *begin(); }
+      {
+	__glibcxx_requires_nonempty();
+	return *begin();
+      }
 
       /**
        *  Returns a read/write reference to the data at the last
@@ -866,7 +894,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       reference
       back() _GLIBCXX_NOEXCEPT
-      { return *(end() - 1); }
+      {
+	__glibcxx_requires_nonempty();
+	return *(end() - 1);
+      }
       
       /**
        *  Returns a read-only (constant) reference to the data at the
@@ -874,7 +905,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_reference
       back() const _GLIBCXX_NOEXCEPT
-      { return *(end() - 1); }
+      {
+	__glibcxx_requires_nonempty();
+	return *(end() - 1);
+      }
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // DR 464. Suggestion for new member functions in standard containers.
@@ -949,6 +983,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       pop_back() _GLIBCXX_NOEXCEPT
       {
+	__glibcxx_requires_nonempty();
 	--this->_M_impl._M_finish;
 	_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
       }
@@ -1051,6 +1086,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       iterator
       insert(const_iterator __position, size_type __n, const value_type& __x)
       {
+	__glibcxx_requires_valid_insert_position(__position);
 	difference_type __offset = __position - cbegin();
 	_M_fill_insert(begin() + __offset, __n, __x);
 	return begin() + __offset;
@@ -1071,7 +1107,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       insert(iterator __position, size_type __n, const value_type& __x)
-      { _M_fill_insert(__position, __n, __x); }
+      {
+	__glibcxx_requires_valid_insert_position(__position);
+	_M_fill_insert(__position, __n, __x);
+      }
 #endif
 
 #if __cplusplus >= 201103L
@@ -1096,6 +1135,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         insert(const_iterator __position, _InputIterator __first,
 	       _InputIterator __last)
         {
+	  __glibcxx_requires_valid_insert_position(__position);
 	  difference_type __offset = __position - cbegin();
 	  _M_insert_dispatch(begin() + __offset,
 			     __first, __last, __false_type());
@@ -1121,6 +1161,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         insert(iterator __position, _InputIterator __first,
 	       _InputIterator __last)
         {
+	  __glibcxx_requires_valid_insert_position(__position);
 	  // Check whether it's an integral type.  If so, it's not an iterator.
 	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 	  _M_insert_dispatch(__position, __first, __last, _Integral());
@@ -1145,10 +1186,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       iterator
 #if __cplusplus >= 201103L
       erase(const_iterator __position)
-      { return _M_erase(begin() + (__position - cbegin())); }
+      {
+	__glibcxx_requires_valid_erase_position(__position);
+	return _M_erase(begin() + (__position - cbegin()));
+      }
 #else
       erase(iterator __position)
-      { return _M_erase(__position); }
+      {
+	__glibcxx_requires_valid_erase_position(__position);
+	return _M_erase(__position);
+      }
 #endif
 
       /**
@@ -1173,13 +1220,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
       erase(const_iterator __first, const_iterator __last)
       {
+	__glibcxx_requires_valid_range(__first, __last);
 	const auto __beg = begin();
 	const auto __cbeg = cbegin();
 	return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg));
       }
 #else
       erase(iterator __first, iterator __last)
-      { return _M_erase(__first, __last); }
+      {
+	__glibcxx_requires_valid_range(__first, __last);
+	return _M_erase(__first, __last);
+      }
 #endif
 
       /**
@@ -1194,6 +1245,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       swap(vector& __x) _GLIBCXX_NOEXCEPT
       {
+#if __cplusplus >= 201103L
+	__glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
+			 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
+#endif
 	this->_M_impl._M_swap_data(__x._M_impl);
 	_Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
 	                          __x._M_get_Tp_allocator());
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 34118a4..965dab3 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -111,6 +111,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     insert(iterator __position, const value_type& __x)
 #endif
     {
+      __glibcxx_requires_valid_insert_position(__position);
       const size_type __n = __position - begin();
       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 	  && __position == end())
@@ -301,6 +302,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       vector<_Tp, _Alloc>::
       emplace(const_iterator __position, _Args&&... __args)
       {
+	__glibcxx_requires_valid_insert_position(__position);
 	const size_type __n = __position - begin();
 	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 	    && __position == end())
diff --git a/libstdc++-v3/include/debug/assertions.h b/libstdc++-v3/include/debug/assertions.h
index 9b9a48c..5e29676 100644
--- a/libstdc++-v3/include/debug/assertions.h
+++ b/libstdc++-v3/include/debug/assertions.h
@@ -33,20 +33,48 @@
 
 # define _GLIBCXX_DEBUG_ASSERT(_Condition)
 # define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
-# define _GLIBCXX_DEBUG_ONLY(_Statement) ;
+# define _GLIBCXX_DEBUG_ONLY(_Statement)
 
+#endif
+
+#ifndef _GLIBCXX_ASSERTIONS
+# define __glibcxx_requires_non_empty_range(_First,_Last)
+# define __glibcxx_requires_valid_range(_First,_Last)
+# define __glibcxx_requires_valid_insert_position(_Position)
+# define __glibcxx_requires_valid_erase_position(_Position)
+# define __glibcxx_requires_nonempty()
+# define __glibcxx_requires_subscript(_N)
 #else
 
-#define _GLIBCXX_DEBUG_ASSERT(_Condition) __glibcxx_assert(_Condition)
+# include <debug/macros.h>
+
+# define __glibcxx_requires_valid_insert_position(_Position)	\
+  __glibcxx_check_insert2(_Position)
+# define __glibcxx_requires_valid_erase_position(_Position)	\
+  __glibcxx_check_erase2(_Position)
+# define __glibcxx_requires_subscript(_N)	\
+  __glibcxx_assert(_N < this->size())
+# define __glibcxx_requires_non_empty_range(_First,_Last)	\
+  __glibcxx_check_non_empty_range(_First,_Last)
+# define __glibcxx_requires_valid_range(_First,_Last)	\
+  __glibcxx_assert(__gnu_debug::__valid_range(_First, _Last))
+# define __glibcxx_requires_nonempty()		\
+  __glibcxx_assert(!this->empty())
+
+# include <debug/helper_functions.h>
 
-#ifdef _GLIBCXX_DEBUG_PEDANTIC
-# define _GLIBCXX_DEBUG_PEDASSERT(_Condition) _GLIBCXX_DEBUG_ASSERT(_Condition)
-#else
-# define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
 #endif
 
-# define _GLIBCXX_DEBUG_ONLY(_Statement) _Statement
+#ifdef _GLIBCXX_DEBUG
+# define _GLIBCXX_DEBUG_ASSERT(_Condition) __glibcxx_assert(_Condition)
 
+# ifdef _GLIBCXX_DEBUG_PEDANTIC
+#  define _GLIBCXX_DEBUG_PEDASSERT(_Condition) _GLIBCXX_DEBUG_ASSERT(_Condition)
+# else
+#  define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
+# endif
+
+# define _GLIBCXX_DEBUG_ONLY(_Statement) _Statement
 #endif
 
 #endif // _GLIBCXX_DEBUG_ASSERTIONS
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index b5935fe..f233bc1 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -74,33 +74,16 @@ namespace __gnu_debug
 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred)
 # define __glibcxx_requires_string(_String)
 # define __glibcxx_requires_string_len(_String,_Len)
-# define __glibcxx_requires_subscript(_N)
 # define __glibcxx_requires_irreflexive(_First,_Last)
 # define __glibcxx_requires_irreflexive2(_First,_Last)
 # define __glibcxx_requires_irreflexive_pred(_First,_Last,_Pred)
 # define __glibcxx_requires_irreflexive_pred2(_First,_Last,_Pred)
 
-#ifdef _GLIBCXX_ASSERTIONS
-// Verify that [_First, _Last) forms a non-empty iterator range.
-# define __glibcxx_requires_non_empty_range(_First,_Last) \
-  __glibcxx_assert(_First != _Last)
-// Verify that the container is nonempty
-# define __glibcxx_requires_nonempty() \
-  __glibcxx_assert(! this->empty())
 #else
-# define __glibcxx_requires_non_empty_range(_First,_Last)
-# define __glibcxx_requires_nonempty()
-#endif
-
-#else
-
-# include <debug/macros.h>
 
 # define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg)
 # define __glibcxx_requires_valid_range(_First,_Last)	\
   __glibcxx_check_valid_range(_First,_Last)
-# define __glibcxx_requires_non_empty_range(_First,_Last)	\
-  __glibcxx_check_non_empty_range(_First,_Last)
 # define __glibcxx_requires_sorted(_First,_Last)	\
   __glibcxx_check_sorted(_First,_Last)
 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)	\
@@ -121,11 +104,9 @@ namespace __gnu_debug
   __glibcxx_check_heap(_First,_Last)
 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred)	\
   __glibcxx_check_heap_pred(_First,_Last,_Pred)
-# define __glibcxx_requires_nonempty() __glibcxx_check_nonempty()
 # define __glibcxx_requires_string(_String) __glibcxx_check_string(_String)
 # define __glibcxx_requires_string_len(_String,_Len)	\
   __glibcxx_check_string_len(_String,_Len)
-# define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N)
 # define __glibcxx_requires_irreflexive(_First,_Last)	\
   __glibcxx_check_irreflexive(_First,_Last)
 # define __glibcxx_requires_irreflexive2(_First,_Last)	\
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
index a2db00d..b628b06 100644
--- a/libstdc++-v3/include/debug/helper_functions.h
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -138,6 +138,7 @@ namespace __gnu_debug
 	  return __dist.first >= 0;
 	}
 
+      // Can't tell so assume it is fine.
       return true;
     }
 
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index c636663..f1ad40f 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -86,6 +86,17 @@ _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
 		      ._M_sequence(*this, "this")			\
 		      ._M_iterator(_Position, #_Position))
 
+/** The same as previous macro but when _Position is not a debug iterator. */
+#if __cplusplus >= 201103L
+# define __glibcxx_check_insert2(_Position)				\
+  __glibcxx_assert(__gnu_debug::__valid_range(this->cbegin(), _Position) \
+		   && __gnu_debug::__valid_range(_Position, this->cend()))
+#else
+# define __glibcxx_check_insert2(_Position)				\
+  __glibcxx_assert(__gnu_debug::__valid_range(this->begin(), _Position) \
+		   && __gnu_debug::__valid_range(_Position, this->end()))
+#endif
+
 /** Verify that we can insert into *this after the iterator _Position.
  *  Insertion into a container after a specific position requires that
  *  the iterator be nonsingular, either dereferenceable or before-begin,
@@ -152,6 +163,19 @@ _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
 		      ._M_sequence(*this, "this")			\
 		      ._M_iterator(_Position, #_Position))
 
+/** Same as above but for normal (non-debug) containers. */
+#if __cplusplus >= 201103L
+# define __glibcxx_check_erase2(_Position)				\
+  __glibcxx_assert(__gnu_debug::__valid_range(this->cbegin(), _Position) && \
+		   __gnu_debug::__valid_range(_Position, this->cend()) && \
+		   _Position != this->cend())
+#else
+# define __glibcxx_check_erase2(_Position)				\
+  __glibcxx_assert(__gnu_debug::__valid_range(this->begin(), _Position) && \
+		   __gnu_debug::__valid_range(_Position, this->end()) && \
+		   _Position != this->end())
+#endif
+
 /** Verify that we can erase the element after the iterator
  * _Position. We can erase the element if the _Position iterator is
  * before a dereferenceable one and references this sequence.
diff --git a/libstdc++-v3/testsuite/23_containers/vector/debug/insert8_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/debug/insert8_neg.cc
new file mode 100644
index 0000000..5d915c2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/debug/insert8_neg.cc
@@ -0,0 +1,41 @@
+// -*- C++ -*-
+
+// Copyright (C) 2015 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-options "-D_GLIBCXX_ASSERTIONS" }
+// { dg-do run { xfail *-*-* } }
+
+#include <iterator>
+
+#include <vector>
+
+void
+test01()
+{
+  std::vector<int> v1, v2;
+
+  v1.push_back(0);
+
+  v1.insert(v1.begin() + 2, v2.begin(), v2.end());
+}
+
+int
+main()
+{
+  test01();
+}