<vector>: orphan after reallocation in _Insert_x has UB

[CaseyCarter]

Compiling this well-formed TU:

#include <iterator>
#include <vector>

using namespace std;

struct I { // demote pointer to input iterator
    using iterator_category = std::input_iterator_tag;
    using value_type = int;
    using difference_type = std::ptrdiff_t;
    using reference = const int&;
    using pointer = void;

    constexpr explicit I(const int* p) : ptr{p} {}

    constexpr bool operator==(const I& that) const {
        return this->ptr == that.ptr;
    }

    constexpr reference operator*() const {
        return *ptr;
    }

    constexpr I& operator++() {
        ++ptr;
        return *this;
    }
    constexpr void operator++(int) {
        ++*this;
    }

    const int* ptr;
};

static constexpr int numbers[33] = { // Just long enough to force a reallocation
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2};

constexpr bool meow() {
    vector<bool> vec;
    vec.insert(vec.end(), I{numbers}, I{numbers + 33});
    return true;
}
static_assert(meow());

with cl /nologo /std:c++20 /EHsc /Od /MTd diagnoses:

repro.cpp
repro.cpp(45): error C2131: expression did not evaluate to a constant
c:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.31.30818\include\vector(2967): note: failure was caused by subtracting pointers to elements of different arrays

clang-cl produces the more informative compiletime call-stack:

repro.cpp(45,15): error: static_assert expression is not an integral constant
      expression
static_assert(meow());
              ^~~~~~
c:\[...]\include\vector(2967,82): note:
      subexpression not valid in a constant expression
            const auto _Off = static_cast<size_type>(_VBITS * (_Pnextiter._Myptr - _Base)) + _Pnextiter._Myoff;
                                                                                 ^
c:\[...]\include\vector(2985,13): note: in call
      to '&vec->_Orphan_range_unlocked(0, 33)'
            _Orphan_range_unlocked(_Offlo, _Offhi);
            ^
c:\[...]\include\vector(2947,13): note: in call
      to '&vec->_Orphan_range(0, 33)'
            _Orphan_range(static_cast<size_type>(_Realloc ? 0 : _Off), this->_Mysize);
            ^
c:\[...]\include\vector(2917,30): note: in call
      to '&vec->_Insert_x({{{&{*new std::_Container_proxy[1]#1}[0], &_Where}, &{*new unsigned int[1]#2}[1], 0}}, 1)'
        size_type _Off     = _Insert_x(_Where, _Count);
                             ^
c:\[...]\include\vector(2816,16): note: in call
      to '&vec->_Insert_n({{{&{*new std::_Container_proxy[1]#1}[0], &_Where}, &{*new unsigned int[1]#2}[1], 0}}, 1, *
      _First)'
        return _Insert_n(_Where, static_cast<size_type>(1), _Val);
               ^
c:\[...]\include\vector(2835,13): note: in call
      to '&vec->insert({{{&{*new std::_Container_proxy[1]#1}[0], &this->begin() + _Off}, &{*new unsigned int[1]#2}[1],
      0}}, * _First)'
            insert(begin() + _Off, *_First);
            ^
c:\[...]\include\vector(2826,9): note: in call to
      '&vec->_Insert({{{nullptr, &_Where}, nullptr, 0}}, {&numbers[32]}, {&numbers[33]}, {})'
        _Insert(_Where, _First, _Last, _Iter_cat_t<_Iter>{});
        ^
reprp.cpp(42,9): note: in call to '&vec->insert({{{nullptr, &vec.end()}, nullptr, 0}},
      {&numbers[0]}, {&numbers[33]})'
    vec.insert(vec.end(), I{numbers}, I{numbers + 33});
        ^
reprp.cpp(45,15): note: in call to 'meow()'
static_assert(meow());
              ^
1 error generated.

Invalid pointer comparison sounds like UB we can't get away with at compile time. It is, but a peek at _Orphan_range:

STL/stl/inc/vector

Lines 3200 to 3220 in 303df3d

	_CONSTEXPR20 void _Orphan_range_unlocked(size_type _Offlo, size_type _Offhi) const {
	const auto _Base = this->_Myvec.data();
	_Iterator_base12** _Pnext = &this->_Myproxy->_Myfirstiter;
	while (*_Pnext) { // test offset from beginning of vector
	const auto& _Pnextiter = static_cast<const_iterator&>(**_Pnext);
	const auto _Temp = *_Pnext; // TRANSITION, VSO-1269037
	if (!_Pnextiter._Myptr) { // orphan the iterator
	_Temp->_Myproxy = nullptr;
	*_Pnext = _Temp->_Mynextiter;
	continue;
	}
	const auto _Off = static_cast<size_type>(_VBITS * (_Pnextiter._Myptr - _Base)) + _Pnextiter._Myoff;
	if (_Off < _Offlo || _Offhi < _Off) {
	_Pnext = &_Temp->_Mynextiter;
	} else { // orphan the iterator
	_Temp->_Myproxy = nullptr;
	*_Pnext = _Temp->_Mynextiter;
	}
	}
	}

shows this is a runtime bug also: computation of _Off for an iterator created when _Base (_Myvec.data()) had a different value results in something ludicrously out-of-range that won't be properly invalidated.

Popping up the call stack, the root cause is in _Insert_x:

STL/stl/inc/vector

Lines 3168 to 3197 in 303df3d

	_CONSTEXPR20 size_type _Insert_x(const_iterator _Where, size_type _Count) {
	difference_type _Off = _Where - begin();
	#if _ITERATOR_DEBUG_LEVEL == 2
	_STL_VERIFY(end() >= _Where, "vector<bool> insert iterator outside range");
	bool _Realloc = capacity() - size() < _Count;
	#endif // _ITERATOR_DEBUG_LEVEL == 2
	if (_Count != 0) {
	if (max_size() - size() < _Count) {
	_Xlen(); // result too long
	}
	// worth doing
	this->_Myvec.resize(this->_Nw(size() + _Count), 0);
	if (empty()) {
	this->_Mysize += _Count;
	} else { // make room and copy down suffix
	iterator _Oldend = end();
	this->_Mysize += _Count;
	_STD copy_backward(begin() + _Off, _Oldend, end());
	}
	#if _ITERATOR_DEBUG_LEVEL == 2
	_Orphan_range(static_cast<size_type>(_Realloc ? 0 : _Off), this->_Mysize);
	#endif // _ITERATOR_DEBUG_LEVEL == 2
	}
	return static_cast<size_type>(_Off);
	}

The call to Myvec.resize on line 3182 can potentially reallocate _Myvec (when _Realloc is true), rendering all outstanding iterators invalid, which manifests the bug when we call _Orphan_range on line 3192.

The fix is straightforward: invalidate before reallocating. Moving the _Orphan_range call before the resize call in _Insert_x corrects the bug.

[miscco]

I really want to find some time to make the vector Tests more exhaustive

[AlexGuteniev]

Is DevCom-1622062 a similar bug?

[StephanTLavavej]

@AlexGuteniev They are definitely different - this GH issue is a vector<bool> issue in _Insert_x, whereas the DevCom issue is a vector<T> repro which doesn't have an _Insert_x.