Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[vector.capacity] p14 The precondition use "and" but should use "or" #5776

Closed
xmh0511 opened this issue Aug 23, 2022 · 26 comments
Closed

[vector.capacity] p14 The precondition use "and" but should use "or" #5776

xmh0511 opened this issue Aug 23, 2022 · 26 comments

Comments

@xmh0511
Copy link
Contributor

xmh0511 commented Aug 23, 2022

[vector.capacity] p14 says

constexpr void resize(size_type sz);

Preconditions: T is Cpp17MoveInsertable and Cpp17DefaultInsertable into *this.

Cpp17MoveInsertable is defined in [containers.container.alloc.reqmts] p2.3

T is Cpp17MoveInsertable into X means that the following expression is well-formed:

  • allocator_traits::construct(m, p, RV)

[containers.container.alloc.reqmts] p2 says

given an lvalue m of type A, a pointer p of type T*, an expression v of type (possibly const) T, and an rvalue rv of type T,

Consider this example:

struct A{
   A() = default;
   A(A const&) = default;
   A(A&&) = delete;
};
int main(){
   std::vector<A> vec{};
   vec.resize(10); // ok
}

However, A is not Cpp17MoveInsertable since allocator_traits<A>::construct(m, p, RV) is ill-formed for A.

@JohelEGP
Copy link
Contributor

I think it's "and" because when sz > capacity(), the first size() elements use Cpp17MoveInsertable and the rest Cpp17DefaultInsertable.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 23, 2022

I think it's "and" because when sz > capacity(), the first size() elements use Cpp17MoveInsertable and the rest Cpp17DefaultInsertable.

But, in other words, when sz < capacity(), the invocation of resize() indeed does not requires the requirement Cpp17MoveInsertable for A, as shown in the example.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 23, 2022

Moreover, consider this example

  std::vector<A> vec{};
  vec.reserve(2);
  std::cout<< vec.capacity()<<std::endl;  // #1
  vec.resize(10);  // #2

#1 prints 2 and #2 still be ok.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 23, 2022

From the comment of the implementation of vector<T>::resize, it says it will default construct the element when sz > the first size(), see https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h#L1004

@JohelEGP
Copy link
Contributor

When you do run out of capacity, you need the former set of requirements. Maybe what you want is to make the precondition of that set conditional. But I don't think that's editorial.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 23, 2022

See my last comment above. I'm not sure whether the implementation didn't obey the requirement, or whether there are some inconsistencies in the standard. At least, according to your opinion, the requirement Cpp17MoveInsertable for void resize(size_type sz); should be conditional.

@frederick-vs-ja
Copy link
Contributor

From the comment of the implementation of vector<T>::resize, it says it will default construct the element when sz > the first size(), see https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h#L1004

The comment doesn't follow the standard terminology, but IIUC the actual implementation is right here. In that case, the libstdc++ implementation is actually default-inserting new elements (with __uninitialized_default_n_a) and moving or copying old ones (with __uninitialized_move_if_noexcept_a).

We can't simply make Cpp17MoveInsertable or Cpp17DefaultInsertable conditional, because "Mandates" is missing here, and the well-formedness requirements, in my opinion, inappropriately appear in "Preconditions".

I think there are several possible defects.

  • [vector.capacity]/16 suggests that old elements are copy-inserted under some conditions, but Cpp17CopyInsertable (which has semantic requirements) is not mentioned in Preconditions.
  • Many named requirements in [container.alloc.reqmts]/2 (e.g. Cpp17DefaultInsertable) are merely requirements for well-formedness, and it's suspicious for them to appear in Preconditions instead of Mandates.
    • Cpp17MoveInsertable and Cpp17CopyInsertable have additional semantic requirements, should they be split?
  • There is implementation divergence on resize: libstdc++ and msvc stl accept the non-move-insertable A, while libc++ rejects it. Currently all of them are conforming IIUC because Cpp17MoveInsertable only appears in Preconditions. If diagnosable parts of Preconditions are moved to Mandates, then the implementation divergence matters. It's not clear to me whether such divergence is intentionally allowed.

Anyway, I don't think this is editorial either. LWG issues seem needed.

@jwakely
Copy link
Member

jwakely commented Aug 23, 2022

But, in other words, when sz < capacity(), the invocation of resize() indeed does not requires the requirement Cpp17MoveInsertable for A, as shown in the example.

Yes, but simply changing the preconditions from "and" to "or" would not help that problem and would be totally wrong. That would imply that resizing when capacity is exceeded has to work for an object that can only be default constructed, but not copied or moved. That's nonsense.

When shrinking the vector, neither Cpp17MoveInsertable nor Cpp17DefaultInsertable is required. When growing within the current capacity, only Cpp17DefaultInsertable is required. When exceeding the capacity, both are required. So the current wording is correct. In general, for an arbitrary call to resize, both are required.

So there is no editorial issue here, and any change to those requirements would be very non-editorial.

@jwakely
Copy link
Member

jwakely commented Aug 23, 2022

  • Cpp17MoveInsertable and Cpp17CopyInsertable have additional semantic requirements, should they be split?

At the time, there was a deliberate decision to not alter those requirements in Mandating the Standard Library:
Clause 21 - Containers library
. That could be revisited now, but I don't know how much support there would be for doing that. It seems out of scope for an LWG issue, a paper would be needed.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 23, 2022

So the current wording is correct.

The wording "and" requires both conditions are true, I think. However, the condition Cpp17MoveInsertable for A is false. This is the issue here.

@JohelEGP
Copy link
Contributor

That just means it's UB.

(3.3)
Preconditions: the conditions that the function assumes to hold whenever it is called; violation of any preconditions results in undefined behavior.

@frederick-vs-ja
Copy link
Contributor

However, the condition Cpp17MoveInsertable for A is false. This is the issue here.

This is not an issue of standard wording or implementations (at this moment). Using such non-Cpp17MoveInsertable A with resize results in UB, and thus implementations may support it as a conforming extension, or reject it.

@jwakely
Copy link
Member

jwakely commented Aug 23, 2022

i.e. the wording is correct. There is no editorial issue here.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 24, 2022

i.e. the wording is correct. There is no editorial issue here.

My original option is

I'm not sure whether the implementation didn't obey the requirement, or whether there are some inconsistencies in the standard.

AFAIK, the implementations of GCC and MSVC regarding resize all support the case when T is not Cpp17MoveInsertable, not sure whether Clang supports this behavior or not since I didn't dig further in Clang's standard library source code, Clang may be similar to GCC here. According to the wording, the behavior would be UB if T is not Cpp17MoveInsertable, however, all major implementations have consistent behavior. Agree that this issue touches the domain that is non-editorial

@frederick-vs-ja
Copy link
Contributor

I'm not sure whether the implementation didn't obey the requirement, or whether there are some inconsistencies in the standard.

Implementations are conforming here IIUC, as currently they are not required to reject non-Cpp17MoveInsertable types.

The standard wording seemly has defects - copy insertion is suggested by the standard and conditionally used by all mainstream implementations (when the move construction is potentially throwing and copy construction is available), but the "Preconditions:" is only mentioning Cpp17MoveInsertable.

This is not limited to vector's resize. Perhaps almost all element-relocating operations of vector and deque are affected. I've tried to submit an LWG issue for this.

Clang may be similar to GCC here

Yes. But libc++ rejects non-(formally-)Cpp17MoveInsertable types when conditional move-or-copy-insertion is used. (Note that Clang can be used together with libc++, libstdc++, and MSVC STL.)

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

According to the wording, the behavior would be UB if T is not Cpp17MoveInsertable, however, all major implementations have consistent behavior.

Which is one possible outcome of UB.

I'm closing this, there is no editorial issue here.

@jwakely jwakely closed this as not planned Won't fix, can't repro, duplicate, stale Aug 24, 2022
@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 24, 2022

Implementations are conforming here IIUC

From certain perspectives, you're right to say implementations are conforming here. Since the violation of precondition results in UB, which means the document imposes no requirement. Implementations are free to do anything here. Since the behaviors of all mainstream implementations are similar, so I think we might expel the behavior from UB.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 24, 2022

@jwakely @JohelEGP @frederick-vs-ja
Even, a copyable-only(i.e. non-moveable) type is wide use in practice as the element type of a vector

struct T{
   T() = default;
   T(T&){} // suppress the implicitly-declared move constructor, and cannot take a rvalue as the argument
};
int main(){
   std::vector<T> vec;
   vec.resize(1024); // UB here since `T` is not Cpp17MoveInsertable
};

Using T as the element type will incur UB?

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

No, that type is Cpp17MoveInsertable into vec. There's no requirement to use a move constructor, just that construction from an rvalue passed to allocator_traits::construct works. You can pass an rvalue to that copy constructor.

Edit: Oh wait, you've edited the code. I was replying to the original that said T(const T&). With that change, your type is not copy insertable or move insertable. It's disgusting too.

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

This issues list is not the right place to learn how vector works.

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

Since the behaviors of all mainstream implementations are similar, so I think we might expel the behavior from UB.

As stated above, libc++ has a static assert. So not the same.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 24, 2022

The modified example was my original thought when wrote the comment. I'm not learning how to use vector, I just want to say the use of T that causes UB is widely used in actually code.

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

No, because you can't use that type at all with vector. Your example doesn't even compile.

@jwakely
Copy link
Member

jwakely commented Aug 24, 2022

T that causes UB is widely used in actually code

I don't think this is true at all.

Type with T(T&) copy constructors and T(T&&) = delete; move constructors are unusual, and perverse, and generally not usable with the standard library containers.

@xmh0511
Copy link
Contributor Author

xmh0511 commented Aug 25, 2022

Your example doesn't even compile.

You're right, this is my oversight. However, the first example is indeed usable in actual code. Such as deep copy an object instead of using shallow copy.

@jwakely
Copy link
Member

jwakely commented Aug 25, 2022

Deleting a move constructor is perverse. If you don't want it to be efficiently movable, just don't define a move constructor. Then you get deep copies of rvalues.

Getting undefined behaviour for such types is fine, they're irregular and unnecessary.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants