forked from cplusplus/draft
/
d1144-object-relocation.bs
1626 lines (1344 loc) · 77.6 KB
/
d1144-object-relocation.bs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<pre class='metadata'>
Title: std::is_trivially_relocatable
Shortname: D1144
Revision: 11
!Draft Revision: 68
Audience: LEWG, EWG
Status: D
Group: WG21
URL:
Editor: Arthur O'Dwyer, arthur.j.odwyer@gmail.com
Markup Shorthands: markdown yes, biblio yes, markup yes
Abstract:
We define a new verb, "relocate," equivalent to a move and a destroy.
For many C++ types, this is implementable "trivially," as a single <code>memcpy</code>.
We propose a standard trait so library writers can detect such types.
We propose a compiler rule that propagates trivial relocatability among Rule-of-Zero types.
Finally, we propose a standard syntax for a user-defined type (e.g. <code>boost::container::static_vector</code>) to warrant
to the implementation that it is trivially relocatable.
Date: 2024-05-06
</pre>
<style>
ins {background-color: #CCFFCC; text-decoration: underline;}
del {background-color: #FFCACA; text-decoration: line-through;}
</style>
# Changelog # {#changelog}
- R11:
- Updated [[ParlayLib]] status; it conforms with P1144 since February 2024.
Updated [[Abseil]] and [[Folly]] status. Added [[PocketPy]] status.
- Introduce `NoThrowInputIterator` for the benefit of `uninitialized_relocate_n`.
- R10 (pre-Tokyo 2024):
- Added implementation experience with [[Abseil]], [[Amadeus]], [[HPX]], [[ParlayLib]], [[StdxError]], and [[Thrust]].
Added <a href="#relevance-of-assignment">§5.2 "Relevance of `operator=`"</a>.
- Wording for `ExecutionPolicy` overloads of the specialized algorithms. Explain why
there are no `ranges` overloads.
- Moved "trivially relocatable class" wording into [class.prop], and increased the similarity
between `[[trivially_relocatable]]` and `[[no_unique_address]]`.
- R9 (pre-Kona 2023):
- Added feature-test macros `__cpp_impl_trivially_relocatable` and `__cpp_lib_trivially_relocatable`.
- Added <a href="#design-non-goals">§3.1 "Design non-goals"</a> and comparison to [[P2785R3]].
- Replaced [[#non-trivial-samples|Appendix C "Examples of non-trivially relocatable class types"]]
with a shorter summary.
- Removed Appendix E "Open questions" as basically redundant with <a href="#pmr-concerns">§5.3 "Confusing interactions with `std::pmr`"</a>.
See ["P1144 PMR koans"](https://quuxplusone.github.io/blog/2023/06/03/p1144-pmr-koans/) (June 2023).
- R8 (pre-Varna 2023):
- [[#wording-dcl.attr.trivreloc|dcl.attr.trivreloc]]: Removed "If a type `T` is declared `trivially_relocatable`,
and `T` is either not move-constructible or not destructible, the program is ill-formed."
This should have been removed in R7 along with "move-constructible, destructible."
- [[#wording-meta.unary.prop|meta.unary.prop]]: Adjusted the precondition of `is_trivially_relocatable_v` to match `is_trivially_copyable_v`.
Removed `is_relocatable_v`, `is_nothrow_relocatable_v` for insufficient motivation (but kept
`concept relocatable` because it expresses semantic requirements).
- Marked `std::relocate` as `[[nodiscard]]`; changed its return type to `remove_cv_t<T>`.
- Rewrote [[#design-goals|§3 "Design goals."]]
- R7 (post-Issaquah 2023):
- Added `std::uninitialized_relocate_backward`, the building block of `vector::insert`.
- Removed "move-constructible, destructible" from the requirements in [[#wording-basic.types.general|basic.types.general]].
Now trivially relocatable types, like trivially copyable types, can be non-relocatable.
- Added [[#applications|table §2.1]] directly comparing this proposal to Folly, BSL, and Qt.
- Added straw poll results from Issaquah; removed much background and discussion
(leaving only notes for the interested reader to consult [[P1144R6]]).
# Introduction and motivation # {#intro}
Given an object type `T` and memory addresses `src` and `dst`,
the phrase "<b><i>relocate</i></b> a `T` from `src` to `dst`" means
"*move-construct* `dst` from `src`, and then immediately *destroy* the object at `src`."
Any type which is both move-constructible and destructible is <b><i>relocatable</i></b>.
A type is <b><i>nothrow relocatable</i></b> if its relocation operation is noexcept, and a type
is <b><i>trivially relocatable</i></b> if its relocation operation is trivial (which,
just like trivial move-construction and trivial copy-construction, means
"tantamount to `memcpy`").
In practice, almost all relocatable types are trivially relocatable: `std::unique_ptr<int>`,
`std::vector<int>`, `std::string` (on libc++ and MSVC), `std::list<int>` (on MSVC).
Examples of non-trivially relocatable types include `std::list<int>` (on libstdc++ and libc++)
and `std::string` (on libstdc++). See [[#non-trivial-samples]] and [[InPractice]].
P1144 allows the library programmer
to <b><i>warrant</i></b> to the compiler that a resource-management type is trivially relocatable.
Explicit warrants are rarely needed because the compiler can infer trivial relocatability for
Rule-of-Zero types. See [[#wording-basic.types.general]].
The most important thing about P1144 relocation is that it is backward compatible and does not
break either API or ABI. P1144 intends simply to legalize the well-understood tricks
that many industry codebases already do (see [[BSL]], [[Folly]], [[Deque]], [[Abseil]]),
not to change the behavior of any existing source code (except to speed it up),
nor to require major work from standard library vendors.
## Who optimizes on this? ## {#applications}
The following optimizations are possible according to P1144's notion of
trivial relocatability. Here's who does these optimizations in practice:
<table>
<tr>
<td></td><td> vector<br> realloc </td><td> type<br> erasure </td><td> fixed-cap<br> move </td><td> vector<br> `erase` </td><td> vector<br> `insert` </td><td> `rotate` </td><td> `swap` </td>
</tr><tr>
<td> Arthur's libc++ `std::is_trivially_relocatable_v<T>` </td><td>
<a href="https://github.com/Quuxplusone/llvm-project/blob/d0c5d3639e/libcxx/include/vector#L936-L942">`vector`</a> </td><td>
no </td><td>
N/A </td><td>
<a href="https://github.com/Quuxplusone/llvm-project/blob/e8b61de07/libcxx/include/vector#L1663-L1669">`vector`</a><br>
(<a href="https://godbolt.org/z/18hvvxjE4">Godbolt</a>) </td><td>
<a href="https://github.com/Quuxplusone/llvm-project/blob/e8b61de07/libcxx/include/vector#L1722-L1732">`vector`</a><br>
(<a href="https://godbolt.org/z/18hvvxjE4">Godbolt</a>) </td><td>
yes, uses `swap_ranges`<br>
(<a href="https://godbolt.org/z/onxrEce6G">Godbolt</a>) </td><td>
<a href="https://github.com/Quuxplusone/llvm-project/blob/e8b61de07/libcxx/include/__algorithm/swap_ranges.h#L59-L75">`swap_ranges`</a><br>
(<a href="https://godbolt.org/z/onxrEce6G">Godbolt</a>) </td>
</tr><tr>
<td> [[BSL]] `bslmf::IsBitwiseMoveable<T>` </td><td>
<a href="https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslstl/bslstl_vector.h#L3374-L3398">`vector`</a> </td><td>
<a href="https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslstl/bslstl_function.h#L116-L131">no</a> </td><td>
? </td><td>
<a href="https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L3769-L3800">`vector`</a> </td><td>
<a href="https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L3606-L3643">`vector`</a> </td><td>
<a href="https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L1707-L1722">`ArrayPrimitives_Imp::rotate`</a>, unused by `bsl::rotate` </td><td>
no </td>
</tr><tr>
<td> [[Folly]] `folly::IsRelocatable<T>` </td><td>
<a href="https://github.com/facebook/folly/blob/080d2a3b82/folly/FBVector.h#L972">`fbvector`</a> </td><td>
<a href="https://github.com/facebook/folly/blob/080d2a3b82/folly/Function.h#L706-L712">no</a> </td><td>
<a href="https://github.com/facebook/folly/blob/080d2a3b82/folly/small_vector.h#L545-L546">`small_vector`</td><td>
<a href="https://github.com/facebook/folly/blob/080d2a3b82/folly/FBVector.h#L1255-L1261">`fbvector`</a> </td><td>
<a href="https://github.com/facebook/folly/blob/080d2a3b82/folly/FBVector.h#L1353-L1355">`fbvector`</a> </td><td>
N/A </td><td>
N/A </td>
</tr><tr>
<td> [[Qt]] `QTypeInfo<T>::isRelocatable` </td><td>
<a href="https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L865-L872">`QList`</a> </td><td>
<a href="https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/kernel/qvariant.h#L73-L94">`QVariant`</a> </td><td>
<a href="https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qvarlengtharray.h#L312-L328">`QVarLengthArray`</a> </td><td>
<a href="https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L842-L863">`QList`</a> </td><td>
<a href="https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L679-L730">`QList`</a> </td><td>
<a href="https://github.com/qt/qtbase/blob/7db28fb/src/corelib/tools/qcontainertools_impl.h#L89-L107">`q_rotate`</a> </td><td>
N/A </td>
</tr><tr>
<td> [[Abseil]] `absl::is_trivially_relocatable<T>` </td><td>
no </td><td>
N/A </td><td>
<a href="https://github.com/abseil/abseil-cpp/blob/7bd9ff910d489658da58251de1317eb3f790a2c6/absl/container/inlined_vector.h#L220-L230">`inlined_vector`</a> </td><td>
<a href="https://github.com/abseil/abseil-cpp/blob/7bd9ff910d489658da58251de1317eb3f790a2c6/absl/container/internal/inlined_vector.h#L896-L919">`inlined_vector`</a> </td><td>
no </td><td>
N/A </td><td>
<a href="https://github.com/abseil/abseil-cpp/blob/7bd9ff910d489658da58251de1317eb3f790a2c6/absl/container/internal/inlined_vector.h#L323-L335">`inlined_vector`</a> </td>
</tr><tr>
<td> [[Amadeus]] `amc::is_trivially_relocatable<T>` </td><td>
<a href="https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/smallvector.hpp#L41-L48">`Vector`</a> </td><td>
N/A </td><td>
<a href="https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L445-L448">`StaticVector`</a> </td><td>
<a href="https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L176-L180">`Vector`</a> </td><td>
<a href="https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L292-L315">`Vector`</a> </td><td>
N/A </td><td>
<a href="https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L201">no</a> </td><td>
</tr>
</table>
### Contiguous reallocation ### {#benefit-resize}
Trivial relocation helps anywhere we do the moral equivalent of `realloc`,
such as in `vector<R>::reserve`.
[[Bench]] (presented at C++Now 2018) shows a 3x speedup on `vector<unique_ptr<int>>::resize`.
[This Reddit thread](https://www.reddit.com/r/cpp/comments/9wj4vt/trivially_relocatable_in_san_diego_call_for/e9p76i4/)
demonstrates a similar 3x speedup using the online tool Quick-Bench.
### Moving in-place/SBO type-erased types like `any` and `function` ### {#benefit-type-erasure}
Trivial relocation can de-duplicate the code generated by type-erasing wrappers
like `any`, `function`, and `move_only_function`.
For these types, a *move* of the wrapper object is implemented in terms of a
*relocation* of the contained object. (E.g.,
<a href="https://github.com/llvm-mirror/libcxx/blob/8fdc4918/include/any#L389-L394">libc++'s `std::any`</a>.)
In general, the *relocate* operation must have a different instantiation for each
different contained type `C`, leading to code bloat. But every trivially relocatable `C`
of a given size can share the same instantiation.
### Moving fixed-capacity containers like `static_vector` and `small_vector` ### {#benefit-fixed-capacity}
The move-constructor of `fixed_capacity_vector<R,N>`
can be implemented naïvely as an element-by-element *move*
(leaving the source vector's elements in their moved-from state),
or efficiently as an element-by-element *relocate*
(leaving the source vector empty).
For detailed analysis, see [[FixedCapacityVector]].
`boost::container::static_vector<R,N>` currently implements the
naïve element-by-element-move strategy, but after LEWG feedback,
[[P0843R5]] `static_vector` does [permit](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0843r5.html#Move-semantics)
the faster relocation strategy.
### Contiguous insert and erase ### {#benefit-insert-erase}
Trivial relocation can be used anywhere we shift a contiguous range left or right,
such as in `vector::erase` (i.e., destroy the erased elements and "close the window"
by memmoving left) and `vector::insert` (i.e., "make a window" by memmoving right and
then construct the new elements in place). [[Folly]]'s `fbvector` does
this optimization; see
<a href="https://github.com/facebook/folly/blob/1d4690d0a3/folly/FBVector.h#L1273-L1308">`fbvector::make_window`</a>.
Bloomberg's [[BSL]] also does this optimization.
### Swap ### {#benefit-swap}
Given a reliable way of detecting trivial relocatability,
we can optimize any routine that uses the moral equivalent of `std::swap`, such as
`std::rotate`, `std::partition`, or `std::sort`.
Optimizing `std::swap` produces massive code-size improvements for all swap-based
algorithms, including `std::sort` and `std::rotate`.
See [[CppNow]] <a href="https://www.youtube.com/watch?v=SGdfPextuAU&t=19m56s">@19:56–21:22</a>,
and see [this Godbolt](https://p1144.godbolt.org/z/PPYhcYd8d).
[This Quick-Bench](https://quick-bench.com/q/suAss7ElmwgLDbOJQGnlEseheSQ) shows a 25% speedup
in `std::rotate` when it is allowed to use bitwise swap on a Rule-of-Zero type.
## Assertions, not assumptions ## {#benefit-assertions}
Some data structures might reasonably assert the trivial relocatability of
their elements, just as they sometimes assert the stronger property of trivial *copyability* today.
This might help them guarantee reasonable performance, or guarantee exception-safety.
For an example of how `std::is_trivially_relocatable` is being used this way in practice,
see [[StdxError]].
## Eliminate manual warrants, improve safety ## {#doing-it-wrong}
Many real-world codebases contain templates which require
trivial relocatability of their template parameters, but cannot today *verify*
trivial relocatability. For example, until 2012 [[Folly]]
[required](https://github.com/facebook/folly/blob/93b0f543f20b8ef3a4c1e34591370011e2dc7168/folly/FBVector.h#L337-L348)
the programmer to warrant the trivial relocatability of any type stored in a `folly::fbvector`:
```cpp
class Widget {
std::vector<int> lst_;
};
folly::fbvector<Widget> vec; // FAIL AT COMPILE TIME for lack of warrant
```
This merely encouraged the programmer to add the warrant and continue. An incorrect
warrant was discovered only at runtime, via undefined behavior. See
[[CppNow]] <a href="https://www.youtube.com/watch?v=SGdfPextuAU&t=27m26s">@27:26–31:47</a>;
for real-world examples see Folly issues [#889](https://github.com/facebook/folly/issues/889),
[#35](https://github.com/facebook/folly/issues/35), [#316](https://github.com/facebook/folly/issues/316),
[#498](https://github.com/facebook/folly/issues/498).
```cpp
class Gadget {
std::list<int> lst_;
};
// sigh, add the warrant on autopilot
template<> struct folly::IsRelocatable<Gadget> : std::true_type {};
folly::fbvector<Gadget> vec; // CRASH AT RUNTIME due to fraudulent warrant
```
> Note: Folly's `fbvector` was [patched](https://github.com/facebook/folly/commit/8dd82d48dd46f43f2ea9b4ed49634a2d3f7ecb43)
> in December 2012 to accept both trivially relocatable and non-trivially relocatable types,
> in line with `std::vector`. Since then, the effect of an incorrect warrant
> remains the same — UB and crash — but a missing warrant simply disables the optimization.
If this proposal is adopted, then Folly can start using `static_assert(std::is_trivially_relocatable_v<T>)`
resp. `if constexpr (std::is_trivially_relocatable_v<T>)`
in the implementation of `fbvector`, and the programmer can stop writing explicit warrants.
Finally, the programmer can start writing assertions of correctness, which aids maintainability and
can even find real bugs. [Example:](https://p1144.godbolt.org/z/7b8893sjr)
```cpp
class Widget {
std::vector<int> lst_;
};
static_assert(std::is_trivially_relocatable_v<Widget>); // correctly SUCCEEDS
class Gadget {
std::list<int> lst_;
};
static_assert(std::is_trivially_relocatable_v<Gadget>); // correctly ERRORS
```
The improvement in user experience and safety in real-world codebases
([[Folly]], [[BSL]], [[Qt]], [[HPX]], [[Amadeus]], [[Abseil]], etc.)
is the most important benefit to be gained by this proposal.
# Design goals # {#design-goals}
Briefly: We want to support all five of the following use-cases ([Godbolt](https://godbolt.org/z/W8e6ansPf)).
```cpp
static_assert(std::is_trivially_relocatable_v<std::unique_ptr<int>>); // #1
struct RuleOfZero { std::unique_ptr<int> p_; };
static_assert(std::is_trivially_relocatable_v<RuleOfZero>); // #2
struct [[trivially_relocatable]] RuleOf3 {
RuleOf3(RuleOf3&&);
RuleOf3& operator=(RuleOf3&&);
~RuleOf3();
};
static_assert(std::is_trivially_relocatable_v<RuleOf3>); // #3
struct [[trivially_relocatable]] Wrap0 {
boost::container::static_vector<int, 10> v_;
static_assert(!std::is_trivially_relocatable_v<decltype(v_)>);
// it's not annotated, but we know it's actually trivial
};
static_assert(std::is_trivially_relocatable_v<Wrap0>); // #4
struct [[trivially_relocatable]] Wrap3 {
Wrap3(Wrap3&&);
Wrap3& operator=(Wrap3&&);
~Wrap3();
int i_;
boost::interprocess::offset_ptr<int> p_ = &i_;
static_assert(!std::is_trivially_relocatable_v<decltype(p_)>);
// it's not trivial, but we preserve our invariant correctly
};
static_assert(std::is_trivially_relocatable_v<Wrap3>); // #5
```
## Non-goals ## {#design-non-goals}
Note: This section was new in P1144R9.
We propose special support for trivially relocatable types, but no particular support for
types that are relocatable in other ways. The two most-frequently-asked scenarios are:
- "Never-empty types," e.g. `gsl::not_null<unique_ptr<int>>`. Such types are not movable (because by design
they never enter a moved-from state), but they are swappable and could in theory be
relocatable (but not via move-and-destroy, since they cannot be moved).
P1144 supports the physical possibility that `is_trivially_relocatable_v<T> && !is_relocatable_v<T>`,
but keeps the status quo w.r.t. library support for such types;
e.g. you can't `resize`, `insert`, or `erase` a `vector` of such types.
P1144's `std::relocate_at` rejects such types.
- Types that are "efficiently but non-trivially relocatable," e.g. libc++'s `tuple<string, list<int>>`,
where the ideal relocation operation would trivially relocate the string and
move-and-destroy the list; this is not trivial, but still faster than move-and-destroy'ing
the whole `tuple`. P1144 keeps the status quo w.r.t. such types, and doesn't
provide any way to optimize their relocation.
See ["Cheaply relocatable, but not trivially relocatable"](https://quuxplusone.github.io/blog/2018/10/26/cheaply-but-not-trivially-relocatable/)
(October 2018).
The most promising active proposal for "non-trivial relocation" is [[P2785R3]]. It proposes a
"relocation constructor" like this:
```cpp
struct A {
A(A) = default;
};
```
which the compiler deduces is trivial iff all of `A`'s members are trivially relocatable.
This solves both of the above "non-goal" scenarios.
However, [[P2785R3]] fails to support our positive goals `Wrap0` and `Wrap3`, which are
trivially relocatable despite having some *non-trivial* members. In other words, P1144 is
forward-compatible with (does not close the door to) [[P2785R3]]; and vice versa,
adopting [[P2785R3]] would not solve two of P1144's five advertised use-cases. WG21 might
well want to adopt both proposals. But P1144 solves "the 99% problem"; P1144 might
not leave enough performance on the table to motivate the further adoption of [[P2785R3]].
Notably, P1144R10 is almost entirely a subset of [[P2785R3]]; the only significant difference
is that [[P2785R3]] doesn't propose the `[[trivially_relocatable]]` warrant itself.
(P2785 proposes that to make a type trivially relocatable, you `=default`
its relocation constructor. P1144 can't do that, and anyway wants to support `Wrap0` and `Wrap3`.)
<small>
<table>
<tr><th>P1144</th><th>P2785R3</th></tr>
<tr><td>`[[trivially_relocatable]]`</td><td></td></tr>
<tr><td></td><td><code>T(T) = default;</code></td></tr>
<tr><td></td><td><code>T& operator=(T) = default;</code></td></tr>
<tr><td>QoI `[[trivially_relocatable]]`<br>on STL containers</td><td>Mandate relocation ctors<br>for all STL containers</td></tr>
<tr><td></td><td><code>T t = reloc u;</code> (ends <code>u</code>'s lifetime)</td></tr>
<tr><td><code>std::is_trivially_relocatable_v<T></code></td><td><code>std::is_trivially_relocatable_v<T></code></td></tr>
<tr><td><code>concept std::relocatable<T></code></td><td></td></tr>
<tr><td><code>std::relocate_at(psrc, pdst);</code></td><td><code>std::construct_at(pdst, reloc *psrc);</code></td></tr>
<tr><td><code>T t = std::relocate(psrc);</code></td><td><code>T t = std::destroy_relocate(psrc);</code></td></tr>
<tr><td><code>FwdIt std::uninitialized_relocate(<br>  InIt, InIt, FwdIt)</code></td><td><code>FwdIt std::uninitialized_relocate(<br>  InIt, InIt, FwdIt)</code></td></tr>
<tr><td><code>pair<InIt, FwdIt> std::uninitialized_relocate_n(<br>  InIt, Size, FwdIt)</code></td><td><code>pair<InIt, FwdIt> std::uninitialized_relocate_n(<br>  InIt, Size, FwdIt)</code></td></tr>
<tr><td><code>Bidi2 std::uninitialized_relocate_backward(<br>  Bidi1, Bidi1, Bidi2)</code></td><td></td></tr>
<tr><td></td><td><code>std::relocate_t</code>, <code>std::relocate</code> tag type</td></tr>
<tr><td></td><td><code>vector<T>::relocate_out(<br>  const_iterator, const_iterator, OutIt) etc.</code></td></tr>
<tr><td></td><td><code>T queue<T>::pop(relocate_t)</code> etc.</td></tr>
</table>
</small>
# Proposed wording for C++26 # {#wording}
The wording in this section is relative to the current working draft.
Note: There is no difficulty in changing the attribute syntax to a contextual-keyword syntax;
the only difference is aesthetic. We can defer that decision to the last minute. This wording
is patterned on the precedent set by `[[no_unique_address]]`.
Note: Our feature-test macros follow the pattern set by `__cpp_impl_coroutine`+`__cpp_lib_coroutine`
and `__cpp_impl_three_way_comparison`+`__cpp_lib_three_way_comparison`.
## Predefined macro names [cpp.predefined] ## {#wording-cpp.predefined}
Add a feature-test macro to the table in
<a href="https://eel.is/c++draft/cpp.predefined#tab:cpp.predefined.ft">[cpp.predefined]</a>:
<small><blockquote>
<pre>
__cpp_impl_three_way_comparison 201907L
<ins>__cpp_impl_trivially_relocatable YYYYMML</ins>
__cpp_implicit_move 202207L
</pre>
</blockquote></small>
## Header `<version>` synopsis [version.syn] ## {#wording-version.syn}
Add a feature-test macro to <a href="https://eel.is/c++draft/version.syn">[version.syn]/2</a>:
<small><blockquote>
<pre>
#define __cpp_lib_transparent_operators 201510L // freestanding, also in <memory>, <functional>
<ins>#define __cpp_lib_trivially_relocatable YYYYMML // freestanding, also in <memory>, <type_traits></ins>
#define __cpp_lib_tuple_element_t 201402L // freestanding, also in <tuple>
</pre>
</blockquote></small>
## Relocation operation [defns.relocation] ## {#wording-defns.relocation}
Add a new section in <a href="http://eel.is/c++draft/intro.defs">[intro.defs]</a>:
<small><blockquote>
<ins><b>relocation operation [defns.relocation]</b></ins>
<p> <ins>the homogeneous binary operation performed by `std::relocate_at`,
consisting of a move construction immediately followed by a destruction of the source object</ins>
</blockquote></small>
## Trivially relocatable class [class.prop] ## {#wording-class.prop}
Note: For the "if supported" wording, compare <a href="https://eel.is/c++draft/dcl.attr.nouniqueaddr#2.sentence-2">[dcl.attr.nouniqueaddr]/2</a>
and <a href="https://eel.is/c++draft/cpp.cond#5.sentence-1">[cpp.cond]/5</a>.
Modify <a href="http://eel.is/c++draft/class.prop">[class.prop]</a> as follows:
<small><blockquote>
<p>1․ A <i>trivially copyable class</i> is a class:
- that has at least one eligible copy constructor, move constructor, copy assignment operator, or move assignment operator ([special], [class.copy.ctor], [class.copy.assign]),
- where each eligible copy constructor, move constructor, copy assignment operator, and move assignment operator is trivial, and
- that has a trivial, non-deleted destructor ([class.dtor]).
<p>2․ A <i>trivial class</i> is a class that is trivially copyable and has one or more eligible default constructors ([class.default.ctor]), all of which are trivial.
[*Note:* In particular, a trivially copyable or trivial class does not have virtual functions or virtual base classes. *— end note*]
<p><ins>x․ A <i>trivially relocatable class</i> is a class:
- <ins>where no eligible copy constructor, move constructor, copy assignment operator, move assignment operator, or destructor is user-provided,</ins>
- <ins>which has no virtual member functions or virtual base classes,</ins>
- <ins>all of whose non-static data members are either of reference type or of trivially relocatable type (<a href="#wording-basic.types.general">[basic.types.general]</a>), and</ins>
- <ins>all of whose base classes are of trivially relocatable type;</ins>
<ins>or a class that is declared with a `trivially_relocatable` attribute with value `true` (<a href="#wording-dcl.attr.trivreloc">[dcl.attr.trivreloc]</a>)
if that attribute is supported by the implementation (<a href="#wording-cpp.cond">[cpp.cond]</a>).</ins>
<p>3․ A class `S` is a <i>standard-layout class</i> if it: [...]
</blockquote></small>
## Trivially relocatable type [basic.types.general] ## {#wording-basic.types.general}
Add a new section in <a href="http://eel.is/c++draft/basic.types.general">[basic.types.general]</a>:
<small><blockquote>
9․ Arithmetic types ([basic.fundamental]), enumeration types, pointer types, pointer-to-member types ([basic.compound]),
`std::nullptr_t`, and <i>cv</i>-qualified versions of these types are collectively called <i>scalar types</i>.
Scalar types, trivially copyable class types ([class.prop]), arrays of such types, and <i>cv</i>-qualified versions
of these types are collectively called <i>trivially copyable types</i>.
Scalar types, trivial class types ([class.prop]), arrays of such types, and <i>cv</i>-qualified versions of these types
are collectively called <i>trivial types</i>. Scalar types, standard-layout class types ([class.prop]), arrays of such types,
and <i>cv</i>-qualified versions of these types are collectively called <i>standard-layout types</i>.
Scalar types, implicit-lifetime class types ([class.prop]), array types, and <i>cv</i>-qualified versions of these types
are collectively called <i>implicit-lifetime types</i>.
<p><ins>x․ Trivially copyable types, trivially relocatable class types (<a href="#wording-class.prop">[class.prop]</a>), arrays of such types,
and <i>cv</i>-qualified versions of these types are collectively called <i>trivially relocatable types</i>.
<p><ins>[*Note:* For a trivially relocatable type, the relocation operation ([defns.relocation]) as performed by,
for example, `std::swap_ranges` or `std::vector::reserve`, is tantamount
to a simple copy of the underlying bytes. *—end note*]</ins>
<p><ins>[*Note:* It is intended that most standard library types be trivially relocatable types. *—end note*]</ins>
10․ A type is a <i>literal type</i> if it is: [...]
</blockquote></small>
## Trivially relocatable attribute [dcl.attr.trivreloc] ## {#wording-dcl.attr.trivreloc}
Note: For the "Recommended practice" wording, compare <a href="https://eel.is/c++draft/dcl.attr.nouniqueaddr#2.sentence-2">[dcl.attr.nouniqueaddr]/2</a>.
Add a new section after <a href="http://eel.is/c++draft/dcl.attr.nouniqueaddr">[dcl.attr.nouniqueaddr]</a>:
<small><blockquote>
<ins>1․ The *attribute-token* `trivially_relocatable` specifies that a class type's relocation operation has no
visible side-effects other than a copy of the underlying bytes, as if by the library function `std::memcpy`.
It may be applied to the definition of a class. It shall appear at most once in each *attribute-list*.
An *attribute-argument-clause* may be present and, if present, shall have the form</ins>
<pre>
<ins>( <i>constant-expression</i> )</ins>
</pre>
<ins>The *constant-expression* shall be an integral constant expression of type `bool`.
If no *attribute-argument-clause* is present, it has the same effect as an *attribute-argument-clause*
of `(true)`.</ins>
<p><ins>2․ If any definition of a class type has a `trivially_relocatable` attribute with value *V*, then each
definition of the same class type shall have a `trivially_relocatable` attribute with value *V*.
No diagnostic is required if definitions in different translation units have
mismatched `trivially_relocatable` attributes.</ins>
<p><ins>3․ If a class type is declared with the `trivially_relocatable` attribute, and the program relies on
observable side-effects of its relocation other than a copy of the underlying bytes, the behavior is undefined.</ins>
<p><ins>4․ *Recommended practice:* The value of a <i>has-attribute-expression</i> for
the `trivially_relocatable` attribute should be `0` for a given implementation unless this attribute
can cause a class type to be trivially relocatable (<a href="#wording-class.prop">[class.prop]</a>).</ins>
</blockquote></small>
### `__has_cpp_attribute` entry [cpp.cond] ### {#wording-cpp.cond}
Add a new entry to the table of supported attributes in
<a href="https://eel.is/c++draft/cpp.cond">[cpp.cond]</a>:
<small><blockquote>
<pre>
noreturn 200809L
<ins>trivially_relocatable YYYYMML</ins>
unlikely 201803L
</pre>
</blockquote></small>
## `relocatable` concept [concept.relocatable] ## {#wording-concept.relocatable}
Add a new section after <a href="http://eel.is/c++draft/concept.copyconstructible">[concept.copyconstructible]</a>:
<small><blockquote>
<ins><b>`relocatable` concept [concept.relocatable]</b></ins>
<p><pre>
<ins>template<class T></ins>
<ins>concept relocatable = move_constructible<T>;</ins>
</pre>
<p><ins>1․ If `T` is an object type, then let `rv` be an rvalue of type `T`, `lv` an lvalue of type `T` equal to `rv`,
and `u2` a distinct object of type `T` equal to `rv`.
`T` models `relocatable` only if</ins>
- <ins>After the definition `T u = rv;`, `u` is equal to `u2`.</ins>
- <ins>`T(rv)` is equal to `u2`.</ins>
- <ins>If the expression `u2 = rv` is well-formed, then the expression has the same semantics as
`u2.~T(); ::new ((void*)std::addressof(u2)) T(rv);`</ins>
- <ins>If the definition `T u = lv;` is well-formed, then after the definition `u` is equal to `u2`.</ins>
- <ins>If the expression `T(lv)` is well-formed, then the expression's result is equal to `u2`.</ins>
- <ins>If the expression `u2 = lv` is well-formed, then the expression has the same semantics as
`u2.~T(); ::new ((void*)std::addressof(u2)) T(lv);`</ins>
</blockquote></small>
Note: We intend that a type may be relocatable
regardless of whether it is copy-constructible; but, if it is copy-constructible then copy-and-destroy
must have the same semantics as move-and-destroy. We intend that a type may be relocatable regardless of
whether it is assignable; but, if it is assignable then assignment must have the same semantics as
destroy-and-copy or destroy-and-move.
The semantic requirements on assignment help us optimize `vector::insert` and `vector::erase`.
`pmr::forward_list<int>` satisfies `relocatable`, but it models `relocatable`
only when all relevant objects have equal allocators.
## Type trait `is_trivially_relocatable` [meta.unary.prop] ## {#wording-meta.unary.prop}
Add a new entry to Table 47 in <a href="http://eel.is/c++draft/meta.unary.prop">[meta.unary.prop]</a>:
<small><blockquote>
<table>
<tr><th>Template</th><th>Condition</th><th>Preconditions</th></tr>
<tr>
<td>`template<class T> struct is_trivially_copyable;`</td>
<td>`T` is a trivially copyable type ([basic.types.general])</td>
<td>`remove_all_extents_t<T>` shall be a complete type or <i>cv</i> `void`.</td>
</tr>
<tr>
<td><ins>`template<class T> struct is_trivially_relocatable;`</ins></td>
<td><ins>`T` is a trivially relocatable type (<a href="#wording-basic.types.general">[basic.types.general]</a>)</ins></td>
<td><ins>`remove_all_extents_t<T>` shall be a complete type or <i>cv</i> `void`.</ins></td>
</tr>
<tr>
<td>`template<class T> struct is_standard_layout;`</td>
<td>`T` is a standard-layout type ([basic.types.general])</td>
<td>`remove_all_extents_t<T>` shall be a complete type or <i>cv</i> `void`.</td>
</tr>
</table>
</blockquote></small>
## `relocate_at` and `relocate` ## {#wording-specialized.relocate}
Note:
These functions have both been implemented in my libc++ fork; for `relocate`, see [this Godbolt](https://p1144.godbolt.org/z/MqPjWfe3e)
and [[StdRelocateIsCute]]. My implementation of their "as-if-by-memcpy" codepaths relies on
Clang's `__builtin_memmove`; vendors can use any vendor-specific means to implement them.
The wording also deliberately permits a low-quality implementation with no such codepath at all.
See [[CppNow]] <a href="https://www.youtube.com/watch?v=SGdfPextuAU&t=45m23s">@45:23–48:39</a>.
Add a new section after <a href="http://eel.is/c++draft/specialized.destroy">[specialized.destroy]</a>:
<small><blockquote>
<ins><b>`relocate` [specialized.relocate]</b></ins>
<p><pre>
<ins>template<class T></ins>
<ins>T *relocate_at(T* source, T* dest);</ins>
</pre>
<p><ins>1․ *Mandates:* `T` is a complete non-array object type.</ins>
<p><ins>2․ *Effects:* Equivalent to:</ins>
<pre>
<ins>struct guard { T *t; ~guard() { destroy_at(t); } } g(source);</ins>
<ins>return ::new (<i>voidify</i>(*dest)) T(std::move(*source));</ins>
</pre>
<ins>except that if `T` is trivially relocatable ([basic.types.general]), side effects
associated with the relocation of the value of `*source` might not happen.</ins>
<pre>
<ins>template<class T></ins>
<ins>[[nodiscard]] remove_cv_t<T> relocate(T* source);</ins>
</pre>
<p><ins>3․ *Mandates:* `T` is a complete non-array object type.</ins>
<p><ins>4․ *Effects:* Equivalent to:</ins>
<pre>
<ins>remove_cv_t<<T> t = std::move(source);</ins>
<ins>destroy_at(source);</ins>
<ins>return t;</ins>
</pre>
<ins>except that if `T` is trivially relocatable ([basic.types]), side effects
associated with the relocation of the object's value might not happen.</ins>
</blockquote></small>
## Nothrow bidirectional iterator [algorithms.requirements] ## {#wording-algorithms.requirements}
Modify <a href="https://eel.is/c++draft/algorithms.requirements">[algorithms.requirements]</a> as follows:
<small><blockquote>
* If an algorithm's template parameter is named `InputIterator`, `InputIterator1`, <del>or</del> `InputIterator2`, <ins>or
`NoThrowInputIterator`,</ins> the template argument shall meet the *Cpp17InputIterator* requirements ([input.iterators]).
* If an algorithm's template parameter is named `OutputIterator`, `OutputIterator1`, or `OutputIterator2`, the template argument
shall meet the `Cpp17OutputIterator` requirements ([output.iterators]).
* If an algorithm's template parameter is named `ForwardIterator`, `ForwardIterator1`,
`ForwardIterator2`, <del>or</del> `NoThrowForwardIterator`, <ins>`NoThrowForwardIterator1`, or `NoThrowForwardIterator2`,</ins> the
template argument shall meet the *Cpp17ForwardIterator* requirements ([forward.iterators]) if it is required to be a mutable iterator,
or model `forward_iterator` ([iterator.concept.forward]) otherwise.
* If an algorithm's template parameter is
named <ins>`NoThrowInputIterator`,</ins> `NoThrowForwardIterator`, <ins>`NoThrowForwardIterator1`, or `NoThrowForwardIterator2`,</ins> the
template argument is also required to have the property that no exceptions are thrown
from increment, assignment, or comparison of, or indirection through, valid iterators.
* If an algorithm's template parameter is named `BidirectionalIterator`,
`BidirectionalIterator1`, <del>or</del> `BidirectionalIterator2`, <ins>`NoThrowBidirectionalIterator1`, or `NoThrowBidirectionalIterator2`,</ins> the
template argument shall meet the *Cpp17BidirectionalIterator* requirements ([bidirectional.iterators])
if it is required to be a mutable iterator, or model `bidirectional_iterator` ([iterator.concept.bidir]) otherwise.
* <ins>If an algorithm's template parameter is named `NoThrowBidirectionalIterator1` or `NoThrowBidirectionalIterator2`, the
template argument is also required to have the property that no exceptions are thrown
from increment, decrement, assignment, or comparison of, or indirection through, valid iterators.</ins>
</blockquote></small>
## `uninitialized_relocate`, `uninitialized_relocate_n`, `uninitialized_relocate_backward` [uninitialized.relocate] ## {#wording-uninitialized.relocate}
Note: Compare to <a href="https://eel.is/c++draft/uninitialized.move">[uninitialized.move]</a> and
<a href="https://eel.is/c++draft/alg.copy">[alg.copy]</a>. The <i>Remarks</i> allude to blanket wording
in <a href="http://eel.is/c++draft/specialized.algorithms#general-2">[specialized.algorithms.general]/2</a>.
Note: I don't propose `ranges::uninitialized_relocate`, because if it worked like `ranges::uninitialized_move`
then it would take two ranges (of possibly different lengths). On success, it would relocate-out-of only
`distance(OR)` elements of `IR`; but if an exception were thrown, it would destroy all the elements of `IR`.
That's a bad contract. Therefore, we omit the `ranges` overloads until someone presents a suitable design.
Modify <a href="http://eel.is/c++draft/memory.syn">[memory.syn]</a> as follows:
<small><blockquote>
<pre>
template<class InputIterator, class NoThrowForwardIterator>
NoThrowForwardIterator uninitialized_move(InputIterator first, // freestanding
InputIterator last,
NoThrowForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator, class NoThrowForwardIterator>
NoThrowForwardIterator uninitialized_move(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
ForwardIterator first, ForwardIterator last,
NoThrowForwardIterator result);
template<class InputIterator, class Size, class NoThrowForwardIterator>
pair<InputIterator, NoThrowForwardIterator>
uninitialized_move_n(InputIterator first, Size n, // freestanding
NoThrowForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator, class Size,
class NoThrowForwardIterator>
pair<ForwardIterator, NoThrowForwardIterator>
uninitialized_move_n(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
ForwardIterator first, Size n, NoThrowForwardIterator result);
namespace ranges {
template<class I, class O>
using uninitialized_move_result = in_out_result<I, O>; // freestanding
template<input_iterator I, sentinel_for<I> S1,
<i>nothrow-forward-iterator</i> O, <i>nothrow-sentinel-for</i><O> S2>
requires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
uninitialized_move_result<I, O>
uninitialized_move(I ifirst, S1 ilast, O ofirst, S2 olast); // freestanding
template<input_range IR, <i>nothrow-forward-range</i> OR>
requires constructible_from<range_value_t<OR>, range_rvalue_reference_t<IR>>
uninitialized_move_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
uninitialized_move(IR&& in_range, OR&& out_range); // freestanding
template<class I, class O>
using uninitialized_move_n_result = in_out_result<I, O>; // freestanding
template<input_iterator I,
<i>nothrow-forward-iterator</i> O, <i>nothrow-sentinel-for</i><O> S>
requires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
uninitialized_move_n_result<I, O>
uninitialized_move_n(I ifirst, iter_difference_t<I> n, // freestanding
O ofirst, S olast);
}
<ins>template<class NoThrowInputIterator, class NoThrowForwardIterator></ins>
<ins>NoThrowForwardIterator uninitialized_relocate(NoThrowInputIterator first,</ins>
<ins>NoThrowInputIterator last,</ins>
<ins>NoThrowForwardIterator result);</ins> <ins>// freestanding</ins>
<ins>template<class ExecutionPolicy, class NoThrowForwardIterator1, class NoThrowForwardIterator2></ins>
<ins>NoThrowForwardIterator2 uninitialized_relocate(ExecutionPolicy&& exec,</ins> <ins>// see [algorithms.parallel.overloads]</ins>
<ins>NoThrowForwardIterator1 first, NoThrowForwardIterator1 last,</ins>
<ins>NoThrowForwardIterator2 result);</ins>
<ins>template<class NoThrowInputIterator, class Size, class NoThrowForwardIterator></ins>
<ins>pair<NoThrowInputIterator, NoThrowForwardIterator></ins>
<ins>uninitialized_relocate_n(NoThrowInputIterator first, Size n,</ins>
<ins>NoThrowForwardIterator result);</ins> <ins>// freestanding</ins>
<ins>template<class ExecutionPolicy, class NoThrowForwardIterator1, class Size,</ins>
<ins>class NoThrowForwardIterator2></ins>
<ins>pair<NoThrowForwardIterator1, NoThrowForwardIterator2></ins>
<ins>uninitialized_relocate_n(ExecutionPolicy&& exec,</ins> <ins>// see [algorithms.parallel.overloads]</ins>
<ins>NoThrowForwardIterator1 first, Size n, NoThrowForwardIterator2 result);</ins>
<ins>template<class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2></ins>
<ins>NoThrowBidirectionalIterator2</ins>
<ins>uninitialized_relocate_backward(NoThrowBidirectionalIterator1 first, BidirectionalIterator1 last,</ins>
<ins>NoThrowBidirectionalIterator2 result);</ins> <ins>// freestanding</ins>
<ins>template<class ExecutionPolicy, class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2></ins>
<ins>NoThrowBidirectionalIterator2</ins>
<ins>uninitialized_relocate_backward(ExecutionPolicy&& exec,</ins>
<ins>NoThrowBidirectionalIterator1 first, NoThrowBidirectionalIterator1 last,</ins>
<ins>NoThrowBidirectionalIterator2 result);</ins> <ins>// freestanding</ins>
template<class NoThrowForwardIterator, class T>
void uninitialized_fill(NoThrowForwardIterator first, // freestanding
NoThrowForwardIterator last, const T& x);
</pre>
</blockquote></small>
Add a new section after <a href="http://eel.is/c++draft/uninitialized.move">[uninitialized.move]</a>:
<small><blockquote>
<ins><b><code>uninitialized_relocate</code> [uninitialized.relocate]</b></ins>
<pre>
<ins>template<class NoThrowInputIterator, class NoThrowForwardIterator></ins>
<ins>NoThrowForwardIterator uninitialized_relocate(NoThrowInputIterator first, NoThrowInputIterator last,</ins>
<ins>NoThrowForwardIterator result);</ins>
</pre>
<p><ins>1․ *Effects:* Equivalent to:</ins>
<pre>
<ins>try {</ins>
<ins>for (; first != last; ++result, (void)++first) {</ins>
<ins>::new (<i>voidify</i>(*result))</ins>
<ins>typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first));</ins>
<ins>destroy_at(addressof(*first));</ins>
<ins>}</ins>
<ins>return result;</ins>
<ins>} catch (...) {</ins>
<ins>destroy(++first, last);</ins>
<ins>throw;</ins>
<ins>}</ins>
</pre>
<ins>except that if the iterators' common value type is trivially relocatable, side effects
associated with the relocation of the object's value might not happen.</ins>
<p><ins>2․ *Remarks:* If an exception is thrown, all objects in both the source and destination
ranges are destroyed.</ins>
<pre>
<ins>template<class NoThrowInputIterator, class Size, class NoThrowForwardIterator></ins>
<ins>pair<NoThrowInputIterator, NoThrowForwardIterator></ins>
<ins>uninitialized_relocate_n(NoThrowInputIterator first, Size n, NoThrowForwardIterator result);</ins>
</pre>
<p><ins>3․ *Effects:* Equivalent to:</ins>
<pre>
<ins>try {</ins>
<ins>for (; n > 0; ++result, (void)++first, --n) {</ins>
<ins>::new (<i>voidify</i>(*result))</ins>
<ins>typename iterator_traits<NoThrowForwardIterator>::value_type(std::move(*first));</ins>
<ins>destroy_at(addressof(*first));</ins>
<ins>}</ins>
<ins>return {first, result};</ins>
<ins>} catch (...) {</ins>
<ins>destroy_n(++first, --n);</ins>
<ins>throw;</ins>
<ins>}</ins>
</pre>
<ins>except that if the iterators' common value type is trivially relocatable, side effects
associated with the relocation of the object's value might not happen.</ins>
<p><ins>4․ *Remarks:* If an exception is thrown, all objects in both the source and destination
ranges are destroyed.</ins>
<pre>
<ins>template<class NoThrowBidirectionalIterator1, class NoThrowBidirectionalIterator2></ins>
<ins>NoThrowBidirectionalIterator2</ins>
<ins>uninitialized_relocate_backward(NoThrowBidirectionalIterator1 first, NoThrowBidirectionalIterator1 last,</ins>
<ins>NoThrowBidirectionalIterator2 result);</ins>
</pre>
<ins>5․ *Effects:* Equivalent to:</ins>
<pre>
<ins>try {</ins>
<ins>for (; last != first; ) {</ins>
<ins>--last;</ins>
<ins>--result;</ins>
<ins>::new (<i>voidify</i>(*result))</ins>
<ins>typename iterator_traits<NoThrowBidirectionalIterator2>::value_type(std::move(*last));</ins>
<ins>destroy_at(addressof(*last));</ins>
<ins>}</ins>
<ins>return result;</ins>
<ins>} catch (...) {</ins>
<ins>destroy(first, ++last);</ins>
<ins>throw;</ins>
<ins>}</ins>
</pre>
<ins>except that if the iterators' common value type is trivially relocatable, side effects
associated with the relocation of the object's value might not happen.</ins>
<p><ins>6․ *Remarks:* If an exception is thrown, all objects in both the source and destination
ranges are destroyed.</ins>
</blockquote></small>
# Rationale and alternatives # {#alternatives}
## Attribute `[[maybe_trivially_relocatable]]` ## {#maybe-trivially-relocatable}
My Clang implementation, currently available on Godbolt, supports both
`[[trivially_relocatable]]` and another attribute called `[[clang::maybe_trivially_relocatable]]`,
as suggested by John McCall in 2018 and also explored by <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2786r0.pdf">P2786R0</a> in 2023.
Where `[[trivially_relocatable]]` is a "sharp knife" that always cuts what you aim it at,
`[[maybe_trivially_relocatable]]` is a "dull knife" that refuses to cut certain materials.
* `[[maybe_trivially_relocatable]]` fails to support [[#design-goals]] examples #4 and #5.
* See <a href="https://quuxplusone.github.io/blog/2023/03/10/sharp-knife-dull-knife/">"Should the compiler sometimes reject a `[[trivially_relocatable]]` warrant?"</a> (2023-03-10).
* See [P1144R4 §6.2](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1144r4.html#maybe-trivially-relocatable).
In Issaquah (February 2023), <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2786r0.pdf">P2786R0</a>
suggested a "dull knife" design similar to `[[clang::maybe_trivially_relocatable]]`.
EWGI took a three-way straw poll on `[[trivially_relocatable]]` versus `[[maybe_trivially_relocatable]]`,
with an inconclusive 7–5–6 vote (the author of P1144 voting "For" and the three representatives of P2786
voting "Against"; i.e. the vote sans authors was 6–5–3).
## Relevance of `operator=` ## {#relevance-of-assignment}
Here's how current implementations define "is trivially relocatable":
<small>
- Mainline Clang `__is_trivially_relocatable(T)`: Trivially move-constructible and trivially destructible, or has `[[clang::trivial_abi]]`
- Arthur's Clang (P1144) `__is_trivially_relocatable(T)`: Trivially copyable, or has `[[clang::trivial_abi]]`, or has `[[trivially_relocatable]]`
- Facebook [[Folly]]'s `folly::IsRelocatable<T>`: `is_trivially_copyable<T>` or has member typedef `T::IsRelocatable`
- Bloomberg [[BSL]]'s `bslmf::IsBitwiseMoveable<T>`: Has a conversion to `bslmf::NestedTraitDeclaration<T, bslmf::IsBitwiseMoveable, true>`,
or has a conversion to `bslmf::NestedTraitDeclaration<T, bslmf::IsBitwiseCopyable, true>`, or `is_trivially_copyable<T>`,
or `sizeof(T) == 1`
- Google [[Abseil]]'s `absl::is_trivially_relocatable<T>`: `is_trivially_copyable<T>`
- [[Amadeus]] AMC's `amc::is_trivially_relocatable<T>`: `is_trivially_copyable<T>` or has member typedef `T::trivially_relocatable`
- Nvidia [[Thrust]]'s `thrust::is_trivially_relocatable<T>`: `is_trivially_copyable<T>`, or `proclaim_trivially_relocatable` is specialized for `T`
- [[HPX]]'s `hpx::experimental::is_trivially_relocatable<T>`: `is_trivially_copyable<T>`, or the trait is specialized for `T`
- [[ParlayLib]]'s `parlay::is_trivially_relocatable<T>`: `is_trivially_copyable<T>`, or `__is_trivially_relocatable(T)` on Clang;
or the trait is specialized for `T`
- [[PocketPy]]'s `pkpy::is_trivially_relocatable_v<T>`: `is_trivially_copyable<T>` and `is_trivially_destructible<T>`, or `TriviallyRelocatable` is specialized for `T`
</small>
Notice that all library implementors (except Parlay on Clang, due to the Clang builtin's current behavior)
agree that a type with trivial move-constructor, trivial destructor, *and non-trivial assignment operator*
is considered non-trivially relocatable. That is, the assignment operator is relevant!
P1144 preserves that behavior, and justifies it by pointing out that relocation
can replace assignment in `vector::erase` and `std::swap`, among other algorithms. Existing codebases (most notably [[Folly]], [[Amadeus]], and [[BSL]])
have written a lot of code that branches on `is_trivially_relocatable`, taking an optimized codepath when `is_trivially_relocatable`
and an unoptimized codepath otherwise. P1144 carefully proposes a definition for `std::is_trivially_relocatable` that keeps
those codebases safe, and that never reports a type `T` as `is_trivially_relocatable` when it's not physically safe
to use `T` with such an optimized codepath.
Here's a worked example showing why [[BSL]] pays attention to the assignment operator:
<small>
```cpp
#include <bsl_vector.h>
using namespace BloombergLP::bslmf;
struct T : NestedTraitDeclaration<T, IsBitwiseMoveable> {
int i_;
T(int i) : i_(i) {}
T(const T&) = default;
void operator=(const T&) noexcept { puts("Called operator="); }
~T() = default;
};
int main() {
bsl::vector<T> v = {1,2};
v.erase(v.begin());
// prints nothing; bsl::vector::erase is optimized
}
struct U {
int i_;
U(int i) : i_(i) {}
U(const U&) = default;
void operator=(const U&) noexcept { puts("Called operator="); }
~U() = default;
};
int main() {
bsl::vector<U> v = {1,2};
v.erase(v.begin());
// prints "Called operator="; BSL believes that a non-defaulted
// assignment operator makes U non-trivially relocatable.
// P1144 agrees. std::is_trivially_relocatable_v<U>
// must remain false, so as not to change the
// behavior of bsl::vector<U>.
}
```
</small>
## Confusing interactions with `std::pmr` ## {#pmr-concerns}
Note: See ["P1144 PMR koans"](https://quuxplusone.github.io/blog/2023/06/03/p1144-pmr-koans/) (June 2023)
for additional analysis of the problem cases.
Note: This section was added in P1144R5, revised in R7, R8, and R10.
Here I assume libc++, where `std::string` is trivially relocatable.
P1144 treats move as an optimization of copy; thus we assume that it always ought to be
safe to replace "copy and destroy" with "move and destroy" (and thus with "relocate").
This is informed by Arthur's experience standardizing "implicit move" in <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1155r3.html">P1155</a>
(C++20) and <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2266r3.html">P2266</a> (C++23).
"Implicit move" affects `pmr` types because their copy differs from their move. [Example](https://godbolt.org/z/sGKhxbsrK):
<small>
```cpp