[Bug libstdc++/110542] New: use of allocated storage after deallocation in a constant expression: std::array of std::vector<bool>

[Bug libstdc++/110542] New: use of allocated storage after deallocation in a constant expression: std::array of std::vector<bool>

[hal.finkel.oss at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

            Bug ID: 110542
           Summary: use of allocated storage after deallocation in a
                    constant expression: std::array of std::vector<bool>
           Product: gcc
           Version: 13.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hal.finkel.oss at gmail dot com
  Target Milestone: ---

For this test case:

```
#include <vector>
#include <array>

struct s_t {
  std::vector<std::array<std::vector<int>, 1>> v;

  constexpr void rz(std::size_t n) {
    v.resize(n);
    for (auto &x : v) for (auto &w : x) w.resize(n);
  }
};

constexpr std::size_t test1() {
  s_t s;
  s.rz(1);
  s.rz(2);
  return 1;
}

int main() {
  static_assert(test1() == 1);
}
```

g++ -std=c++20 13.1.0 (and GCC trunk as of today on https://gcc.godbolt.org/):
ERROR:

```
tc1.cpp: In function ‘int main()’:
tc1.cpp:21:25: error: non-constant condition for static assertion
   21 |   static_assert(test1() == 1);
      |                 ~~~~~~~~^~~~
tc1.cpp:21:22:   in ‘constexpr’ expansion of ‘test1()’
tc1.cpp:16:7:   in ‘constexpr’ expansion of ‘s.s_t::rz(2)’
tc1.cpp:9:49:   in ‘constexpr’ expansion of ‘(&
w)->std::vector<int>::resize(n)’
/gcc-13.1.0/include/c++/13/bits/stl_vector.h:1011:21:   in ‘constexpr’
expansion of
‘((std::vector<int>*)this)->std::vector<int>::_M_default_append((__new_size -
((std::vector<int>*)this)->std::vector<int>::size()))’
/gcc-13.1.0/include/c++/13/bits/vector.tcc:676:16:   in ‘constexpr’ expansion
of ‘std::vector<int>::_S_relocate(__old_start, __old_finish, __new_start, (*
&((std::vector<int>*)this)->std::vector<int>::<anonymous>.std::_Vector_base<int,
std::allocator<int> >::_M_get_Tp_allocator()))’
/gcc-13.1.0/include/c++/13/bits/stl_vector.h:504:26:   in ‘constexpr’ expansion
of ‘std::__relocate_a<int*, int*, allocator<int> >(__first, __last, __result,
(* & __alloc))’
/gcc-13.1.0/include/c++/13/bits/stl_uninitialized.h:1142:33:   in ‘constexpr’
expansion of ‘std::__relocate_a_1<int, int>(std::__niter_base<int*>(__first),
std::__niter_base<int*>(__last), std::__niter_base<int*>(__result), (* &
__alloc))’
/gcc-13.1.0/include/c++/13/bits/stl_uninitialized.h:1122:35:   in ‘constexpr’
expansion of ‘std::__relocate_a_1<int*, __gnu_cxx::__normal_iterator<int*,
void>, allocator<int> >(__first, __last, __out, (* & __alloc))’
/gcc-13.1.0/include/c++/13/bits/stl_uninitialized.h:1100:26:   in ‘constexpr’
expansion of ‘std::__relocate_object_a<int, int, allocator<int>
>(std::__addressof<int>((* & __cur.__gnu_cxx::__normal_iterator<int*,
void>::operator*())), std::__addressof<int>((* __first)), (* & __alloc))’
/gcc-13.1.0/include/c++/13/bits/stl_uninitialized.h:1072:26:   in ‘constexpr’
expansion of ‘std::allocator_traits<std::allocator<int> >::construct<int,
int>((* & __alloc), __dest, (* & std::move<int&>((*(int*)__orig))))’
/gcc-13.1.0/include/c++/13/bits/alloc_traits.h:539:21:   in ‘constexpr’
expansion of ‘std::construct_at<int, int>(__p, (* & std::forward<int>((* &
__args#0))))’
tc1.cpp:21:25: error: use of allocated storage after deallocation in a constant
expression
In file included from /gcc-13.1.0/include/c++/13/vector:63,
                 from tc1.cpp:1:
/gcc-13.1.0/include/c++/13/bits/allocator.h:195:52: note: allocated here
  195 |             return static_cast<_Tp*>(::operator new(__n));
      |                                      ~~~~~~~~~~~~~~^~~~~

```

clang -std=c++20 15, (and 16 and trunk as of today on https://gcc.godbolt.org/,
noting that these appear to use headers from libstdc++ gcc-12.2.0; below is
from clang 15 using GCC 13.1.0 headers): ERROR:

```
tc1.cpp:21:17: error: static assertion expression is not an integral constant
expression
  static_assert(test1() == 1);
                ^~~~~~~~~~~~
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_algobase.h:931:11:
note: assignment to object outside its lifetime is not allowed in a constant
expression
        *__first = __tmp;
                 ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_algobase.h:977:7:
note: in call to '__fill_a1(&{*new int[2]#4}[1], &{*new int[2]#4}[2], {*new
int[2]#4}[0])'
    { std::__fill_a1(__first, __last, __value); }
      ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_algobase.h:1128:7:
note: in call to '__fill_a(&{*new int[2]#4}[1], &{*new int[2]#4}[2], {*new
int[2]#4}[0])'
      std::__fill_a(__first, __first + __n, __value);
      ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_algobase.h:1157:14:
note: in call to '__fill_n_a(&{*new int[2]#4}[1], 1, {*new int[2]#4}[0],
{{{{}}}})'
      return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
             ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_uninitialized.h:668:18:
note: in call to 'fill_n(&{*new int[2]#4}[1], 1, {*new int[2]#4}[0])'
              __first = std::fill_n(__first, __n - 1, *__val);
                        ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_uninitialized.h:704:14:
note: in call to '__uninit_default_n(&{*new int[2]#4}[1], 2)'
      return __uninitialized_default_n_1<__is_trivial(_ValueType)
             ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_uninitialized.h:773:14:
note: (skipping 1 call in backtrace; use -fconstexpr-backtrace-limit=0 to see
all)
    { return std::__uninitialized_default_n(__first, __n); }
             ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/vector.tcc:668:9:
note: in call to '__uninitialized_default_n_a(&{*new int[2]#4}[0], 2, {*new
std::array<std::vector<int>, 1>[2]#2}[1]._M_elems[0]._Vector_base::_M_impl)'
                      std::__uninitialized_default_n_a(__new_start + __size,
                      ^
/gcc-13.1.0/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/stl_vector.h:1011:4:
note: in call to '&{*new std::array<std::vector<int>,
1>[2]#2}[1]._M_elems[0]->_M_default_append(2)'
          _M_default_append(__new_size - size());
          ^
tc1.cpp:9:43: note: in call to '&{*new std::array<std::vector<int>,
1>[2]#2}[1]._M_elems[0]->resize(2)'
    for (auto &x : v) for (auto &w : x) w.resize(n);
                                          ^
tc1.cpp:16:5: note: in call to '&s->rz(2)'
  s.rz(2);
    ^
tc1.cpp:21:17: note: in call to 'test1()'
  static_assert(test1() == 1);
                ^
1 error generated.

```

clang -std=c++20 -stdlib=libc++ 15, 16, and trunk as of today on
https://gcc.godbolt.org/): OK

I realize that this might be two compiler bugs, and I see, e.g., GCC bug
101777, but the fact that both GCC and clang provide what seem like they might
be the same semantic error, a use after deallocation, albeit pointing at
slightly different places in the libstdc++ headers, both on the second resize,
and it works with libc++, is why I suspect that it might be an issue in the
library (and the error message here is different from the one in 101777). Or,
of course, my code has UB and the compilers are correct.

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-07-04
             Status|UNCONFIRMED                 |NEW

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
There seem to be two separate bugs here, which I don't understand.

The clang error is fixed by:

--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -661,6 +661,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
         {
          if (__n > 0)
            {
+#ifdef __cpp_lib_is_constant_evaluated
+             if (std::is_constant_evaluated())
+               return __uninitialized_default_n_1<false>::
+                        __uninit_default_n(__first, __n);
+#endif
              typename iterator_traits<_ForwardIterator>::value_type* __val
                = std::__addressof(*__first);
              std::_Construct(__val);

But this doesn't fix the error with GCC.

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I don't understand why GCC *doesn't* fail without the fix above, when that code
clearly gets used during constant evaluation and the runtime version of that
function *does* access objects outside their lifetime (the *__first = __tmp
expression shown in the Clang output).

And I don't understand why GCC *does* fail in __relocate_object, which looks
correct to me (and Clang happily compiles).

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The GCC error is fixed by this change:

--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -701,6 +701,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
              pointer __old_start = this->_M_impl._M_start;
              pointer __old_finish = this->_M_impl._M_finish;

+             _Tp val;
+             if (__old_start != __old_finish)
+               val = std::move(*__old_start);
+
              const size_type __len =
                _M_check_len(__n, "vector::_M_default_append");
              pointer __new_start(this->_M_allocate(__len));

Which makes no sense whatsoever, as it's just a redundant read from
*__old_start, which cannot change whether or not that pointer has already been
deallocated when read from again later!

So I think this part is a GCC bug.

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #3)
> +               val = std::move(*__old_start);

If this is changed to just val = *__old_start then the error comes back.

110542.cc: In function 'int main()':
110542.cc:23:25: error: non-constant condition for static assertion
   23 |   static_assert(test1() == 1);
      |                 ~~~~~~~~^~~~
110542.cc:23:22:   in 'constexpr' expansion of 'test1()'
110542.cc:18:7:   in 'constexpr' expansion of 's.s_t::rz(2)'
110542.cc:11:49:   in 'constexpr' expansion of '(&
w)->std::vector<int>::resize(n)'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:1014:21:   in
'constexpr' expansion of
'((std::vector<int>*)this)->std::vector<int>::_M_default_append((__new_size -
((std::vector<int>*)this)->std::vector<int>::size()))'
110542.cc:23:25: error: use of allocated storage after deallocation in a
constant expression

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:83cae6c4b788544635a71748e1881c150f42efef

commit r14-2306-g83cae6c4b788544635a71748e1881c150f42efef
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 4 16:03:45 2023 +0100

    libstdc++: Fix std::__uninitialized_default_n for constant evaluation
[PR110542]

    libstdc++-v3/ChangeLog:

            PR libstdc++/110542
            * include/bits/stl_uninitialized.h (__uninitialized_default_n):
            Do not use std::fill_n during constant evaluation.

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 55475
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55475&action=edit
Reduced test case

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #55475|0                           |1
        is obsolete|                            |

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 55477
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55477&action=edit
Reduced test case

Slightly further reduced, so it compiles successfully with clang.

GCC gives:

110542.cc: In function 'int main()':
110542.cc:23:25: error: non-constant condition for static assertion
   23 |   static_assert(test1() == 1);
      |                 ~~~~~~~~^~~~
110542.cc:23:22:   in 'constexpr' expansion of 'test1()'
110542.cc:18:7:   in 'constexpr' expansion of 's.s_t::rz(2)'
110542.cc:11:49:   in 'constexpr' expansion of '(&
w)->std::vector<int>::resize(n)'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:1014:28:   in
'constexpr' expansion of
'((std::vector<int>*)this)->std::vector<int>::_M_default_append((__new_size -
((std::vector<int>*)this)->std::vector<int>::size()))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/vector.tcc:177:24:   in
'constexpr' expansion of 'std::vector<int>::_S_relocate(__old_start,
__old_finish, __new_start, (*
&((std::vector<int>*)this)->std::vector<int>::<anonymous>.std::_Vector_base<int,
std::allocator<int> >::_M_get_Tp_allocator()))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:497:35:   in
'constexpr' expansion of 'std::__relocate_a<int*, int*, allocator<int>
>(__first, __last, __result, (* & __alloc))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:1134:33:   in
'constexpr' expansion of 'std::__relocate_a_1<int,
int>(std::__niter_base<int*>(__first), std::__niter_base<int*>(__last),
std::__niter_base<int*>(__result), (* & __alloc))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:1114:37:   in
'constexpr' expansion of 'std::__relocate_object_a<int, int, allocator<int>
>(std::__addressof<int>((* __cur)), std::__addressof<int>((* __first)), (* &
__alloc))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:1065:26:   in
'constexpr' expansion of 'std::allocator_traits<std::allocator<int>
>::construct<int, int>((* & __alloc), __dest, (* &
std::move<int&>((*(int*)__orig))))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/alloc_traits.h:539:21:   in
'constexpr' expansion of 'std::construct_at<int, int>(__p, (* &
std::forward<int>((* & __args#0))))'
110542.cc:23:25: error: use of allocated storage after deallocation in a
constant expression
/home/jwakely/gcc/14/include/c++/14.0.0/bits/allocator.h:195:52: note:
allocated here
  195 |             return static_cast<_Tp*>(::operator new(__n));
      |                                      ~~~~~~~~~~~~~~^~~~~

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #55477|0                           |1
        is obsolete|                            |

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 55483
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55483&action=edit
Further reduced test case

This compiles with both Clang and EDG, but not GCC:

$ g++ -std=c++20  a-110542.ii
In file included from
/home/jwakely/gcc/14/include/c++/14.0.0/bits/vector.tcc:89,
                 from /home/jwakely/gcc/14/include/c++/14.0.0/vector:69,
                 from 110542.cc:2:
110542.cc: In function 'int main()':
110542.cc:23:25: error: non-constant condition for static assertion
   23 |   static_assert(test1() == 1);
      |                 ~~~~~~~~^~~~
110542.cc:23:22:   in 'constexpr' expansion of 'test1()'
110542.cc:18:7:   in 'constexpr' expansion of 's.s_t::rz(2)'
110542.cc:11:49:   in 'constexpr' expansion of '(&
w)->std::vector<int>::resize(n)'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:268:28:   in
'constexpr' expansion of
'((std::vector<int>*)this)->std::vector<int>::_M_default_append((__new_size -
((std::vector<int>*)this)->std::vector<int>::size()))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/vector.tcc:73:28:   in 'constexpr'
expansion of 'std::__relocate_a<int, int>(__old_start, __old_finish,
__new_start, (*
&((std::vector<int>*)this)->std::vector<int>::<anonymous>.std::_Vector_base<int,
std::allocator<int> >::_M_get_Tp_allocator()))'
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:30:26:   in
'constexpr' expansion of 'std::construct_at<int, int>(__result, (* &
std::move<int&>((* __first))))'
110542.cc:23:25: error: use of allocated storage after deallocation in a
constant expression
In file included from /home/jwakely/gcc/14/include/c++/14.0.0/vector:63:
/home/jwakely/gcc/14/include/c++/14.0.0/bits/allocator.h:195:55: note:
allocated here
  195 |             return static_cast<_Tp*>(::operator new(__n));
      |                                         ~~~~~~~~~~~~~~^~~~

[Bug libstdc++/110542] use of allocated storage after deallocation in a constant expression: std::array of std::vector<int>

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110542

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:a32d4a34da72087c9f9bdfe3f987b808be814cd7

commit r13-7580-ga32d4a34da72087c9f9bdfe3f987b808be814cd7
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 4 16:03:45 2023 +0100

    libstdc++: Fix std::__uninitialized_default_n for constant evaluation
[PR110542]

    libstdc++-v3/ChangeLog:

            PR libstdc++/110542
            * include/bits/stl_uninitialized.h (__uninitialized_default_n):
            Do not use std::fill_n during constant evaluation.

    (cherry picked from commit 83cae6c4b788544635a71748e1881c150f42efef)