vec.h: Make some ops work with non-trivially copy constructible and/or destructible types

  Hi!

We have some very limited support for non-POD types in vec.h
(in particular grow_cleared will invoke default ctors on the
cleared elements and vector copying invokes copy ctors.

My pending work on wide_int/widest_int which makes those two
non-trivially default/copy constructible, assignable and destructible
shows this isn't enough though.
In particular the uses of it in irange shows that quick_push
still uses just assignment operator rather than copy construction
and we never invoke destructors on anything.

The following patch does that for quick_push (copy construction
using placement new rather than assignment, for trivially copy
constructible types I think it should be the same) and invokes
destructors (only if non-trivially destructible) in pop, release
and truncate.  Now as discussed last night on IRC, the pop case
is problematic, because our pop actually does two things,
it decreases length (so the previous last element should be destructed)
but also returns a reference to it.  We have some 300+ uses of this
and the reference rather than returning it by value is useful at least
for the elements which are (larger) POD structures, so I'm not
prepared to change that.  Though obviously for types with non-trivial
destructors returning a reference to just destructed element is not
a good idea.  So, this patch for that case only makes pop return void
instead and any users wishing to get the last element need to use last ()
and pop () separately (currently there are none).

Note, a lot of vec.h operations is still not friendly for non-POD types,
I've added a comment for quick_insert and ordered_remove, but qsort is
such a case as well and in fact most others too.  For non-POD, I'd say
with this patch it is safe just to {quick,safe}_grow_cleared (but not
just *_grow), {quick,safe}_push, pop, truncate, release, copy
them around and ops which do not add/remove any elements or move them
around.  And obviously using non-trivially destructible types in
va_gc vectors is undesirable as well.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2023-09-27  Jakub Jelinek  <jakub@redhat.com>

	* vec.h (vec_destruct): New function template.
	(release): Use it for non-trivially destructible T.
	(truncate): Likewise.
	(quick_push): Perform a placement new into slot
	instead of assignment.
	(quick_insert, ordered_remove): Note that they aren't suitable
	for non-PODs.
	(pop): For non-trivially destructible T return void
	rather than T & and destruct the popped element.
	* edit-context.cc (class line_event): Move definition earlier.


	Jakub
  

On Wed, 27 Sep 2023, Jakub Jelinek wrote:

> Hi!
> 
> We have some very limited support for non-POD types in vec.h
> (in particular grow_cleared will invoke default ctors on the
> cleared elements and vector copying invokes copy ctors.
> 
> My pending work on wide_int/widest_int which makes those two
> non-trivially default/copy constructible, assignable and destructible
> shows this isn't enough though.
> In particular the uses of it in irange shows that quick_push
> still uses just assignment operator rather than copy construction
> and we never invoke destructors on anything.
> 
> The following patch does that for quick_push (copy construction
> using placement new rather than assignment, for trivially copy
> constructible types I think it should be the same) and invokes
> destructors (only if non-trivially destructible) in pop, release
> and truncate.  Now as discussed last night on IRC, the pop case
> is problematic, because our pop actually does two things,
> it decreases length (so the previous last element should be destructed)
> but also returns a reference to it.  We have some 300+ uses of this
> and the reference rather than returning it by value is useful at least
> for the elements which are (larger) POD structures, so I'm not
> prepared to change that.  Though obviously for types with non-trivial
> destructors returning a reference to just destructed element is not
> a good idea.  So, this patch for that case only makes pop return void
> instead and any users wishing to get the last element need to use last ()
> and pop () separately (currently there are none).
> 
> Note, a lot of vec.h operations is still not friendly for non-POD types,
> I've added a comment for quick_insert and ordered_remove, but qsort is
> such a case as well and in fact most others too.  For non-POD, I'd say
> with this patch it is safe just to {quick,safe}_grow_cleared (but not
> just *_grow), {quick,safe}_push, pop, truncate, release, copy
> them around and ops which do not add/remove any elements or move them
> around.  And obviously using non-trivially destructible types in
> va_gc vectors is undesirable as well.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK I guess.  Can you summarize the limitations for non-POD types
in the big comment at the start of vec.h?  (can we put in static_asserts
in the places that obviously do not work?)

Thanks,
Richard.

> 2023-09-27  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* vec.h (vec_destruct): New function template.
> 	(release): Use it for non-trivially destructible T.
> 	(truncate): Likewise.
> 	(quick_push): Perform a placement new into slot
> 	instead of assignment.
> 	(quick_insert, ordered_remove): Note that they aren't suitable
> 	for non-PODs.
> 	(pop): For non-trivially destructible T return void
> 	rather than T & and destruct the popped element.
> 	* edit-context.cc (class line_event): Move definition earlier.
> 
> --- gcc/vec.h.jj	2023-09-26 16:44:30.637902359 +0200
> +++ gcc/vec.h	2023-09-26 21:17:30.366534474 +0200
> @@ -185,6 +185,16 @@ extern void dump_vec_loc_statistics (voi
>  /* Hashtable mapping vec addresses to descriptors.  */
>  extern htab_t vec_mem_usage_hash;
>  
> +/* Destruct N elements in DST.  */
> +
> +template <typename T>
> +inline void
> +vec_destruct (T *dst, unsigned n)
> +{
> +  for ( ; n; ++dst, --n)
> +    dst->~T ();
> +}
> +
>  /* Control data for vectors.  This contains the number of allocated
>     and used slots inside a vector.  */
>  
> @@ -310,6 +320,9 @@ va_heap::release (vec<T, va_heap, vl_emb
>    if (v == NULL)
>      return;
>  
> +  if (!std::is_trivially_destructible <T>::value)
> +    vec_destruct (v->address (), v->length ());
> +
>    if (GATHER_STATISTICS)
>      v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
>  				  v->allocated (), true);
> @@ -588,7 +601,10 @@ public:
>    void splice (const vec &);
>    void splice (const vec *src);
>    T *quick_push (const T &);
> -  T &pop (void);
> +  using pop_ret_type
> +    = typename std::conditional <std::is_trivially_destructible <T>::value,
> +				 T &, void>::type;
> +  pop_ret_type pop (void);
>    void truncate (unsigned);
>    void quick_insert (unsigned, const T &);
>    void ordered_remove (unsigned);
> @@ -1005,19 +1021,24 @@ vec<T, A, vl_embed>::quick_push (const T
>  {
>    gcc_checking_assert (space (1));
>    T *slot = &address ()[m_vecpfx.m_num++];
> -  *slot = obj;
> +  ::new (static_cast<void*>(slot)) T (obj);
>    return slot;
>  }
>  
>  
> -/* Pop and return the last element off the end of the vector.  */
> +/* Pop and return a reference to the last element off the end of the
> +   vector.  If T has non-trivial destructor, this method just pops
> +   the element and returns void type.  */
>  
>  template<typename T, typename A>
> -inline T &
> +inline typename vec<T, A, vl_embed>::pop_ret_type
>  vec<T, A, vl_embed>::pop (void)
>  {
>    gcc_checking_assert (length () > 0);
> -  return address ()[--m_vecpfx.m_num];
> +  T &last = address ()[--m_vecpfx.m_num];
> +  if (!std::is_trivially_destructible <T>::value)
> +    last.~T ();
> +  return static_cast <pop_ret_type> (last);
>  }
>  
>  
> @@ -1028,13 +1049,16 @@ template<typename T, typename A>
>  inline void
>  vec<T, A, vl_embed>::truncate (unsigned size)
>  {
> -  gcc_checking_assert (length () >= size);
> +  unsigned l = length ();
> +  gcc_checking_assert (l >= size);
> +  if (!std::is_trivially_destructible <T>::value)
> +    vec_destruct (address () + l, l - size);
>    m_vecpfx.m_num = size;
>  }
>  
>  
>  /* Insert an element, OBJ, at the IXth position of this vector.  There
> -   must be sufficient space.  */
> +   must be sufficient space.  This operation is not suitable for non-PODs.  */
>  
>  template<typename T, typename A>
>  inline void
> @@ -1050,7 +1074,7 @@ vec<T, A, vl_embed>::quick_insert (unsig
>  
>  /* Remove an element from the IXth position of this vector.  Ordering of
>     remaining elements is preserved.  This is an O(N) operation due to
> -   memmove.  */
> +   memmove.  Not suitable for non-PODs.  */
>  
>  template<typename T, typename A>
>  inline void
> @@ -1518,7 +1542,10 @@ public:
>    void safe_splice (const vec & CXX_MEM_STAT_INFO);
>    T *quick_push (const T &);
>    T *safe_push (const T &CXX_MEM_STAT_INFO);
> -  T &pop (void);
> +  using pop_ret_type
> +    = typename std::conditional <std::is_trivially_destructible <T>::value,
> +				 T &, void>::type;
> +  pop_ret_type pop (void);
>    void truncate (unsigned);
>    void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
>    void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
> @@ -1986,10 +2013,12 @@ vec<T, va_heap, vl_ptr>::safe_push (cons
>  }
>  
>  
> -/* Pop and return the last element off the end of the vector.  */
> +/* Pop and return a reference to the last element off the end of the
> +   vector.  If T has non-trivial destructor, this method just pops
> +   last element and returns void.  */
>  
>  template<typename T>
> -inline T &
> +inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
>  vec<T, va_heap, vl_ptr>::pop (void)
>  {
>    return m_vec->pop ();
> --- gcc/edit-context.cc.jj	2023-01-02 09:32:43.106985882 +0100
> +++ gcc/edit-context.cc	2023-09-26 19:39:20.213374419 +0200
> @@ -122,6 +122,32 @@ class added_line
>    int m_len;
>  };
>  
> +/* Class for representing edit events that have occurred on one line of
> +   one file: the replacement of some text betweeen some columns
> +   on the line.
> +
> +   Subsequent events will need their columns adjusting if they're
> +   are on this line and their column is >= the start point.  */
> +
> +class line_event
> +{
> + public:
> +  line_event (int start, int next, int len) : m_start (start),
> +    m_delta (len - (next - start)) {}
> +
> +  int get_effective_column (int orig_column) const
> +  {
> +    if (orig_column >= m_start)
> +      return orig_column += m_delta;
> +    else
> +      return orig_column;
> +  }
> +
> + private:
> +  int m_start;
> +  int m_delta;
> +};
> +
>  /* The state of one edited line within an edited_file.
>     As well as the current content of the line, it contains a record of
>     the changes, so that further changes can be applied in the correct
> @@ -172,32 +198,6 @@ class edited_line
>    auto_vec <added_line *> m_predecessors;
>  };
>  
> -/* Class for representing edit events that have occurred on one line of
> -   one file: the replacement of some text betweeen some columns
> -   on the line.
> -
> -   Subsequent events will need their columns adjusting if they're
> -   are on this line and their column is >= the start point.  */
> -
> -class line_event
> -{
> - public:
> -  line_event (int start, int next, int len) : m_start (start),
> -    m_delta (len - (next - start)) {}
> -
> -  int get_effective_column (int orig_column) const
> -  {
> -    if (orig_column >= m_start)
> -      return orig_column += m_delta;
> -    else
> -      return orig_column;
> -  }
> -
> - private:
> -  int m_start;
> -  int m_delta;
> -};
> -
>  /* Forward decls.  */
>  
>  static void
> 
> 	Jakub
> 
>