-
Notifications
You must be signed in to change notification settings - Fork 22
/
p1900r0.html
867 lines (857 loc) · 78.9 KB
/
p1900r0.html
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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang xml:lang>
<head>
<meta charset="utf-8" />
<meta name="generator" content="mpark/wg21" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<meta name="dcterms.date" content="2019-10-06" />
<title>Concepts-Adjacent Problems</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<style>
code.sourceCode > span { display: inline-block; line-height: 1.25; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
{ counter-reset: source-line 0; }
pre.numberSource code > span
{ position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
{ content: counter(source-line);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
color: #aaaaaa;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
div.sourceCode
{ background-color: #f6f8fa; }
@media screen {
code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
code span. { } /* Normal */
code span.al { color: #ff0000; } /* Alert */
code span.an { } /* Annotation */
code span.at { } /* Attribute */
code span.bn { color: #9f6807; } /* BaseN */
code span.bu { color: #9f6807; } /* BuiltIn */
code span.cf { color: #00607c; } /* ControlFlow */
code span.ch { color: #9f6807; } /* Char */
code span.cn { } /* Constant */
code span.co { color: #008000; font-style: italic; } /* Comment */
code span.cv { color: #008000; font-style: italic; } /* CommentVar */
code span.do { color: #008000; } /* Documentation */
code span.dt { color: #00607c; } /* DataType */
code span.dv { color: #9f6807; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #9f6807; } /* Float */
code span.fu { } /* Function */
code span.im { } /* Import */
code span.in { color: #008000; } /* Information */
code span.kw { color: #00607c; } /* Keyword */
code span.op { color: #af1915; } /* Operator */
code span.ot { } /* Other */
code span.pp { color: #6f4e37; } /* Preprocessor */
code span.re { } /* RegionMarker */
code span.sc { color: #9f6807; } /* SpecialChar */
code span.ss { color: #9f6807; } /* SpecialString */
code span.st { color: #9f6807; } /* String */
code span.va { } /* Variable */
code span.vs { color: #9f6807; } /* VerbatimString */
code span.wa { color: #008000; font-weight: bold; } /* Warning */
code.diff {color: #898887}
code.diff span.va {color: #006e28}
code.diff span.st {color: #bf0303}
</style>
<style type="text/css">
body {
margin: 5em;
font-family: serif;
hyphens: auto;
line-height: 1.35;
}
div.wrapper {
max-width: 60em;
margin: auto;
}
ul {
list-style-type: none;
padding-left: 2em;
margin-top: -0.2em;
margin-bottom: -0.2em;
}
a {
text-decoration: none;
color: #4183C4;
}
a.hidden_link {
text-decoration: none;
color: inherit;
}
li {
margin-top: 0.6em;
margin-bottom: 0.6em;
}
h1, h2, h3, h4 {
position: relative;
line-height: 1;
}
a.self-link {
position: absolute;
top: 0;
left: calc(-1 * (3.5rem - 26px));
width: calc(3.5rem - 26px);
height: 2em;
text-align: center;
border: none;
transition: opacity .2s;
opacity: .5;
font-family: sans-serif;
font-weight: normal;
font-size: 83%;
}
a.self-link:hover { opacity: 1; }
a.self-link::before { content: "§"; }
ul > li:before {
content: "\2014";
position: absolute;
margin-left: -1.5em;
}
:target { background-color: #C9FBC9; }
:target .codeblock { background-color: #C9FBC9; }
:target ul { background-color: #C9FBC9; }
.abbr_ref { float: right; }
.folded_abbr_ref { float: right; }
:target .folded_abbr_ref { display: none; }
:target .unfolded_abbr_ref { float: right; display: inherit; }
.unfolded_abbr_ref { display: none; }
.secnum { display: inline-block; min-width: 35pt; }
.header-section-number { display: inline-block; min-width: 35pt; }
.annexnum { display: block; }
div.sourceLinkParent {
float: right;
}
a.sourceLink {
position: absolute;
opacity: 0;
margin-left: 10pt;
}
a.sourceLink:hover {
opacity: 1;
}
a.itemDeclLink {
position: absolute;
font-size: 75%;
text-align: right;
width: 5em;
opacity: 0;
}
a.itemDeclLink:hover { opacity: 1; }
span.marginalizedparent {
position: relative;
left: -5em;
}
li span.marginalizedparent { left: -7em; }
li ul > li span.marginalizedparent { left: -9em; }
li ul > li ul > li span.marginalizedparent { left: -11em; }
li ul > li ul > li ul > li span.marginalizedparent { left: -13em; }
div.footnoteNumberParent {
position: relative;
left: -4.7em;
}
a.marginalized {
position: absolute;
font-size: 75%;
text-align: right;
width: 5em;
}
a.enumerated_item_num {
position: relative;
left: -3.5em;
display: inline-block;
margin-right: -3em;
text-align: right;
width: 3em;
}
div.para { margin-bottom: 0.6em; margin-top: 0.6em; text-align: justify; }
div.section { text-align: justify; }
div.sentence { display: inline; }
span.indexparent {
display: inline;
position: relative;
float: right;
right: -1em;
}
a.index {
position: absolute;
display: none;
}
a.index:before { content: "⟵"; }
a.index:target {
display: inline;
}
.indexitems {
margin-left: 2em;
text-indent: -2em;
}
div.itemdescr {
margin-left: 3em;
}
.bnf {
font-family: serif;
margin-left: 40pt;
margin-top: 0.5em;
margin-bottom: 0.5em;
}
.ncbnf {
font-family: serif;
margin-top: 0.5em;
margin-bottom: 0.5em;
margin-left: 40pt;
}
.ncsimplebnf {
font-family: serif;
font-style: italic;
margin-top: 0.5em;
margin-bottom: 0.5em;
margin-left: 40pt;
background: inherit;
}
span.textnormal {
font-style: normal;
font-family: serif;
white-space: normal;
display: inline-block;
}
span.rlap {
display: inline-block;
width: 0px;
}
span.descr { font-style: normal; font-family: serif; }
span.grammarterm { font-style: italic; }
span.term { font-style: italic; }
span.terminal { font-family: monospace; font-style: normal; }
span.nonterminal { font-style: italic; }
span.tcode { font-family: monospace; font-style: normal; }
span.textbf { font-weight: bold; }
span.textsc { font-variant: small-caps; }
a.nontermdef { font-style: italic; font-family: serif; }
span.emph { font-style: italic; }
span.techterm { font-style: italic; }
span.mathit { font-style: italic; }
span.mathsf { font-family: sans-serif; }
span.mathrm { font-family: serif; font-style: normal; }
span.textrm { font-family: serif; }
span.textsl { font-style: italic; }
span.mathtt { font-family: monospace; font-style: normal; }
span.mbox { font-family: serif; font-style: normal; }
span.ungap { display: inline-block; width: 2pt; }
span.textit { font-style: italic; }
span.texttt { font-family: monospace; }
span.tcode_in_codeblock { font-family: monospace; font-style: normal; }
span.phantom { color: white; }
span.math { font-style: normal; }
span.mathblock {
display: block;
margin-left: auto;
margin-right: auto;
margin-top: 1.2em;
margin-bottom: 1.2em;
text-align: center;
}
span.mathalpha {
font-style: italic;
}
span.synopsis {
font-weight: bold;
margin-top: 0.5em;
display: block;
}
span.definition {
font-weight: bold;
display: block;
}
.codeblock {
margin-left: 1.2em;
line-height: 127%;
}
.outputblock {
margin-left: 1.2em;
line-height: 127%;
}
div.itemdecl {
margin-top: 2ex;
}
code.itemdeclcode {
white-space: pre;
display: block;
}
span.textsuperscript {
vertical-align: super;
font-size: smaller;
line-height: 0;
}
.footnotenum { vertical-align: super; font-size: smaller; line-height: 0; }
.footnote {
font-size: small;
margin-left: 2em;
margin-right: 2em;
margin-top: 0.6em;
margin-bottom: 0.6em;
}
div.minipage {
display: inline-block;
margin-right: 3em;
}
div.numberedTable {
text-align: center;
margin: 2em;
}
div.figure {
text-align: center;
margin: 2em;
}
table {
border: 1px solid black;
border-collapse: collapse;
margin-left: auto;
margin-right: auto;
margin-top: 0.8em;
text-align: left;
hyphens: none;
}
td, th {
padding-left: 1em;
padding-right: 1em;
vertical-align: top;
}
td.empty {
padding: 0px;
padding-left: 1px;
}
td.left {
text-align: left;
}
td.right {
text-align: right;
}
td.center {
text-align: center;
}
td.justify {
text-align: justify;
}
td.border {
border-left: 1px solid black;
}
tr.rowsep, td.cline {
border-top: 1px solid black;
}
tr.even, tr.odd {
border-bottom: 1px solid black;
}
tr.capsep {
border-top: 3px solid black;
border-top-style: double;
}
tr.header {
border-bottom: 3px solid black;
border-bottom-style: double;
}
th {
border-bottom: 1px solid black;
}
span.centry {
font-weight: bold;
}
div.table {
display: block;
margin-left: auto;
margin-right: auto;
text-align: center;
width: 90%;
}
span.indented {
display: block;
margin-left: 2em;
margin-bottom: 1em;
margin-top: 1em;
}
ol.enumeratea { list-style-type: none; background: inherit; }
ol.enumerate { list-style-type: none; background: inherit; }
code.sourceCode > span { display: inline; }
div#refs p { padding-left: 32px; text-indent: -32px; }
</style>
<style type="text/css">a {
color : #4183C4;
text-decoration: underline;
}
a.marginalized {
text-decoration: none;
}
a.self-link {
text-decoration: none;
}
h1#toctitle {
border-bottom: 1px solid #cccccc;
}
#TOC li {
margin-top: 1px;
margin-bottom: 1px;
}
#TOC ul>li:before { display: none; }
h3.subtitle { margin-top: -15px; }
h1:target { background-color: transparent; }
h2:target { background-color: transparent; }
h3:target { background-color: transparent; }
h4:target { background-color: transparent; }
h5:target { background-color: transparent; }
h6:target { background-color: transparent; }
code span.co { font-family: monospace; }
table tr {
background-color: white;
}
table tr:nth-child(2n) {
background-color: #f6f8fa;
}
#title-block-header > table tr:nth-child(2n) {
background-color: white;
}
td > div.sourceCode {
background-color: inherit;
}
table {
border-collapse: collapse;
}
table td, table th {
border: 1px solid #cccccc;
}
table th {
border-bottom: 1px solid black;
text-align: center;
}
table tr:first-child th {
border-top: 0;
}
table tr:last-child td {
border-bottom: 0;
}
table tr td:first-child,
table tr th:first-child {
border-left: 0;
}
table tr td:last-child,
table tr th:last-child {
border-right: 0;
}
table tbody tr:first-child td {
border-top: 1px solid black;
}
#title-block-header td { border: 0; }
@media all {
body {
margin: 2em;
}
}
@media screen and (min-width: 480px) {
body {
margin: 5em;
}
}
#refs code{padding-left: 0px; text-indent: 0px;}
:root {
--diff-ins: #e6ffed;
--diff-strongins: #acf2bd;
--diff-del: #ffdddd;
--diff-strongdel: #ff8888;
}
span.diffins {
background-color: var(--diff-strongins);
}
span.diffdel {
background-color: var(--diff-strongdel);
}
div.rm { text-decoration: line-through; }
div.rm code.sourceCode { text-decoration: line-through; }
div.addu, span.addu {
color: #006e28;
background-color: var(--diff-ins);
}
div.rm pre, div.add pre { background-color: #f6f8fa; }
div.addu pre { background-color: var(--diff-ins); }
div.add, div.add pre { background-color: var(--diff-ins); }
div.addu blockquote {
border-left: 4px solid #00a000;
padding: 0 15px;
color: #006e28;
text-decoration: none;
}
div.addu blockquote code.sourceCode { text-decoration: none; }
div.addu blockquote pre { text-decoration: none; }
div.addu blockquote pre code { text-decoration: none; }
code.diff span.va { color: #000000; background-color: var(--diff-ins); }
code.diff span.st { color: #000000; background-color: var(--diff-del); }
</style>
<link href="data:image/vnd.microsoft.icon;base64,AAABAAIAEBAAAAEAIABoBAAAJgAAACAgAAABACAAqBAAAI4EAAAoAAAAEAAAACAAAAABACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA////AIJEAACCRAAAgkQAAIJEAACCRAAAgkQAVoJEAN6CRADegkQAWIJEAACCRAAAgkQAAIJEAACCRAAA////AP///wCCRAAAgkQAAIJEAACCRAAsgkQAvoJEAP+CRAD/gkQA/4JEAP+CRADAgkQALoJEAACCRAAAgkQAAP///wD///8AgkQAAIJEABSCRACSgkQA/IJEAP99PQD/dzMA/3czAP99PQD/gkQA/4JEAPyCRACUgkQAFIJEAAD///8A////AHw+AFiBQwDqgkQA/4BBAP9/PxP/uZd6/9rJtf/bybX/upd7/39AFP+AQQD/gkQA/4FDAOqAQgBc////AP///wDKklv4jlEa/3o7AP+PWC//8+3o///////////////////////z7un/kFox/35AAP+GRwD/mVYA+v///wD///8A0Zpk+NmibP+0d0T/8evj///////+/fv/1sKz/9bCs//9/fr//////+/m2/+NRwL/nloA/5xYAPj///8A////ANKaZPjRmGH/5cKh////////////k149/3UwAP91MQD/lmQ//86rhv+USg3/m1YA/5hSAP+bVgD4////AP///wDSmmT4zpJY/+/bx///////8+TV/8mLT/+TVx//gkIA/5lVAP+VTAD/x6B//7aEVv/JpH7/s39J+P///wD///8A0ppk+M6SWP/u2sf///////Pj1f/Nj1T/2KFs/8mOUv+eWhD/lEsA/8aee/+0glT/x6F7/7J8Rvj///8A////ANKaZPjRmGH/48Cf///////+/v7/2qt//82PVP/OkFX/37KJ/86siv+USg7/mVQA/5hRAP+bVgD4////AP///wDSmmT40ppk/9CVXP/69O////////7+/v/x4M//8d/P//7+/f//////9u7n/6tnJf+XUgD/nFgA+P///wD///8A0ppk+NKaZP/RmWL/1qNy//r07///////////////////////+vXw/9akdP/Wnmn/y5FY/6JfFvj///8A////ANKaZFTSmmTo0ppk/9GYYv/Ql1//5cWm//Hg0P/x4ND/5cWm/9GXYP/RmGH/0ppk/9KaZOjVnmpY////AP///wDSmmQA0ppkEtKaZI7SmmT60ppk/9CWX//OkVb/zpFW/9CWX//SmmT/0ppk/NKaZJDSmmQS0ppkAP///wD///8A0ppkANKaZADSmmQA0ppkKtKaZLrSmmT/0ppk/9KaZP/SmmT/0ppkvNKaZCrSmmQA0ppkANKaZAD///8A////ANKaZADSmmQA0ppkANKaZADSmmQA0ppkUtKaZNzSmmTc0ppkVNKaZADSmmQA0ppkANKaZADSmmQA////AP5/AAD4HwAA4AcAAMADAACAAQAAgAEAAIABAACAAQAAgAEAAIABAACAAQAAgAEAAMADAADgBwAA+B8AAP5/AAAoAAAAIAAAAEAAAAABACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA////AP///wCCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAAyCRACMgkQA6oJEAOqCRACQgkQAEIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAA////AP///wD///8A////AIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRABigkQA5oJEAP+CRAD/gkQA/4JEAP+CRADqgkQAZoJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAAD///8A////AP///wD///8AgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAA4gkQAwoJEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQAxIJEADyCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAAgkQAAP///wD///8A////AP///wCCRAAAgkQAAIJEAACCRAAAgkQAAIJEAACCRAAWgkQAmIJEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAJyCRAAYgkQAAIJEAACCRAAAgkQAAIJEAACCRAAA////AP///wD///8A////AIJEAACCRAAAgkQAAIJEAACCRAAAgkQAdIJEAPCCRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAP+CRAD/gkQA/4JEAPSCRAB4gkQAAIJEAACCRAAAgkQAAIJEAAD///8A////AP///wD///8AgkQAAIJEAACCRAAAgkQASoJEANKCRAD/gkQA/4JEAP+CRAD/g0YA/39AAP9zLgD/bSQA/2shAP9rIQD/bSQA/3MuAP9/PwD/g0YA/4JEAP+CRAD/gkQA/4JEAP+CRADUgkQAToJEAACCRAAAgkQAAP///wD///8A////AP///wB+PwAAgkUAIoJEAKiCRAD/gkQA/4JEAP+CRAD/hEcA/4BBAP9sIwD/dTAA/5RfKv+viF7/vp56/76ee/+wiF7/lWAr/3YxAP9sIwD/f0AA/4RHAP+CRAD/gkQA/4JEAP+CRAD/gkQArIJEACaBQwAA////AP///wD///8A////AIBCAEBzNAD6f0EA/4NFAP+CRAD/gkQA/4VIAP92MwD/bSUA/6N1Tv/ezsL/////////////////////////////////38/D/6V3Uv9uJgD/dTEA/4VJAP+CRAD/gkQA/4JEAP+BQwD/fUAA/4FDAEj///8A////AP///wD///8AzJRd5qBlKf91NgD/dDUA/4JEAP+FSQD/cy4A/3YyAP/PuKP//////////////////////////////////////////////////////9K7qP94NQD/ciwA/4VJAP+CRAD/fkEA/35BAP+LSwD/mlYA6v///wD///8A////AP///wDdpnL/4qx3/8KJUv+PUhf/cTMA/3AsAP90LgD/4dK+/////////////////////////////////////////////////////////////////+TYxf91MAD/dTIA/31CAP+GRwD/llQA/6FcAP+gWwD8////AP///wD///8A////ANGZY/LSm2X/4ap3/92mcP+wdT3/byQA/8mwj////////////////////////////////////////////////////////////////////////////+LYxv9zLgP/jUoA/59bAP+hXAD/nFgA/5xYAPL///8A////AP///wD///8A0ppk8tKaZP/RmWL/1p9q/9ubXv/XqXj////////////////////////////7+fD/vZyG/6BxS/+gcUr/vJuE//r37f//////////////////////3MOr/5dQBf+dVQD/nVkA/5xYAP+cWAD/nFgA8v///wD///8A////AP///wDSmmTy0ppk/9KaZP/SmWP/yohJ//jo2P//////////////////////4NTG/4JDFf9lGAD/bSQA/20kAP9kGAD/fz8S/+Xb0f//////5NG9/6txN/+LOgD/m1QA/51aAP+cWAD/m1cA/5xYAP+cWADy////AP///wD///8A////ANKaZPLSmmT/0ppk/8+TWf/Unmv//v37//////////////////////+TWRr/VwsA/35AAP+ERgD/g0UA/4JGAP9lHgD/kFga/8KXX/+TRwD/jT4A/49CAP+VTQD/n10A/5xYAP+OQQD/lk4A/55cAPL///8A////AP///wD///8A0ppk8tKaZP/SmmT/y4tO/92yiP//////////////////////8NnE/8eCQP+rcTT/ez0A/3IyAP98PgD/gEMA/5FSAP+USwD/jj8A/5lUAP+JNwD/yqV2/694Mf+HNQD/jkAA/82rf/+laBj/jT4A8v///wD///8A////AP///wDSmmTy0ppk/9KaZP/LiUr/4byY///////////////////////gupX/0I5P/+Wuev/Lklz/l1sj/308AP+QSwD/ol0A/59aAP+aVQD/k0oA/8yoh///////+fXv/6pwO//Lp3v///////Pr4f+oay7y////AP///wD///8A////ANKaZPLSmmT/0ppk/8uJSv/hvJj//////////////////////+G7l//Jhkb/0ppk/96nc//fqXX/x4xO/6dkFP+QSQD/llEA/5xXAP+USgD/yaOA///////38uv/qG05/8ijdv//////8efb/6ZpLPL///8A////AP///wD///8A0ppk8tKaZP/SmmT/zIxO/9yxh///////////////////////7dbA/8iEQf/Sm2X/0Zlj/9ScZv/eqHf/2KJv/7yAQf+XTgD/iToA/5lSAP+JNgD/yKFv/611LP+HNQD/jT8A/8qmeP+kZRT/jT4A8v///wD///8A////AP///wDSmmTy0ppk/9KaZP/Pk1n/1J5q//78+//////////////////+/fv/1aFv/8iEQv/Tm2b/0ppl/9GZY//Wn2z/1pZc/9eldf/Bl2b/kUcA/4w9AP+OQAD/lUwA/59eAP+cWQD/jT8A/5ZOAP+eXADy////AP///wD///8A////ANKaZPLSmmT/0ppk/9KZY//KiEn/8d/P///////////////////////47+f/05tm/8iCP//KiEj/yohJ/8eCP//RmGH//vfy///////n1sP/rXQ7/4k4AP+TTAD/nVoA/5xYAP+cVwD/nFgA/5xYAPL///8A////AP///wD///8A0ppk8tKaZP/SmmT/0ptl/8uLTf/aq37////////////////////////////+/fz/6c2y/961jv/etY7/6Myx//78+v//////////////////////3MWv/5xXD/+ORAD/mFQA/51ZAP+cWAD/nFgA8v///wD///8A////AP///wDSmmTy0ppk/9KaZP/SmmT/0ppk/8mFRP/s1b//////////////////////////////////////////////////////////////////////////////+PD/0JFU/7NzMv+WUQD/kUsA/5tXAP+dWQDy////AP///wD///8A////ANKaZP/SmmT/0ppk/9KaZP/Sm2X/z5NZ/8yMT//z5NX/////////////////////////////////////////////////////////////////9Ofa/8yNUP/UmGH/36p5/8yTWv+qaSD/kksA/5ROAPz///8A////AP///wD///8A0ppk5NKaZP/SmmT/0ppk/9KaZP/TnGf/zY9T/82OUv/t1sD//////////////////////////////////////////////////////+7Yw//OkFX/zI5R/9OcZ//SmmP/26V0/9ymdf/BhUf/ol8R6P///wD///8A////AP///wDSmmQ80ppk9tKaZP/SmmT/0ppk/9KaZP/TnGj/zpFW/8qJSv/dson/8uHS//////////////////////////////////Lj0//etIv/y4lL/86QVf/TnGj/0ppk/9KaZP/RmWP/05xn/9ymdfjUnWdC////AP///wD///8A////ANKaZADSmmQc0ppkotKaZP/SmmT/0ppk/9KaZP/Tm2b/0Zli/8qJSf/NjlH/16Z3/+G8mP/myKr/5siq/+G8mP/Xp3f/zY5S/8qISf/RmGH/05tm/9KaZP/SmmT/0ppk/9KaZP/SmmSm0pljINWdaQD///8A////AP///wD///8A0ppkANKaZADSmmQA0ppkQtKaZMrSmmT/0ppk/9KaZP/SmmT/0ptl/9GYYf/Nj1P/y4lL/8qISP/KiEj/y4lK/82PU//RmGH/0ptl/9KaZP/SmmT/0ppk/9KaZP/SmmTO0ppkRtKaZADSmmQA0ppkAP///wD///8A////AP///wDSmmQA0ppkANKaZADSmmQA0ppkANKaZGzSmmTu0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmTw0ppkcNKaZADSmmQA0ppkANKaZADSmmQA////AP///wD///8A////ANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZBLSmmSQ0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppklNKaZBTSmmQA0ppkANKaZADSmmQA0ppkANKaZAD///8A////AP///wD///8A0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQy0ppkutKaZP/SmmT/0ppk/9KaZP/SmmT/0ppk/9KaZP/SmmT/0ppkvtKaZDbSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkAP///wD///8A////AP///wDSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkXNKaZODSmmT/0ppk/9KaZP/SmmT/0ppk5NKaZGDSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA////AP///wD///8A////ANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkBtKaZIbSmmTo0ppk6tKaZIrSmmQK0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZADSmmQA0ppkANKaZAD///8A////AP/8P///+B///+AH//+AAf//AAD//AAAP/AAAA/gAAAHwAAAA8AAAAPAAAADwAAAA8AAAAPAAAADwAAAA8AAAAPAAAADwAAAA8AAAAPAAAADwAAAA8AAAAPAAAADwAAAA+AAAAfwAAAP/AAAP/8AAP//gAH//+AH///4H////D//" rel="icon" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<div class="wrapper">
<header id="title-block-header">
<h1 class="title" style="text-align:center">Concepts-Adjacent Problems</h1>
<table style="border:none;float:right">
<tr>
<td>Document #: </td>
<td>P1900R0</td>
</tr>
<tr>
<td>Date: </td>
<td>2019-10-06</td>
</tr>
<tr>
<td style="vertical-align:top">Project: </td>
<td>Programming Language C++<br>
EWG<br>
</td>
</tr>
<tr>
<td style="vertical-align:top">Reply-to: </td>
<td>
Barry Revzin<br><<a href="mailto:[email protected]" class="email">[email protected]</a>><br>
</td>
</tr>
</table>
</header>
<div style="clear:both">
<h1 id="introduction" style="border-bottom:1px solid #cccccc"><span class="header-section-number">1</span> Introduction<a href="#introduction" class="self-link"></a></h1>
<p>This paper is not a proposal. It does not offer any concrete suggestions of additions, changes, or removals from C++20. I don’t yet have specific solutions to offer. My goal with this paper is to present a set of problems that I believe should be solved, in an effort to both raise awareness about them and to motivate finding a solution for them.</p>
<p>One of the marquee features of C++20 is Concepts. C++20 Concepts are a language feature that was set out to solve the problem of constraining templates and overload sets. They offer many significant improvements over the C++17 status quo; there are many problems with become straightforwardly and easily solveable with constraints that used to be either impossible or of sufficient difficulty and verbosity that only a small handful of experts, that were sufficiently motivated, could solve them:</p>
<ul>
<li><p>Constraining non-template functions of class templates. Notably, constraining the special member functions of class templates.</p></li>
<li><p>Having multiple constrained overloads, without having to be exceedingly careful in ensuring that all of them are disjointly constrained.</p></li>
<li><p>Constraining class template partial specializations, both in the multiply constrained case (as above) and without having to have the primary class template opt-in to such constrained specializations (i.e. as <code class="sourceCode cpp">std<span class="op">::</span>hash<span class="op"><</span>T<span class="op">></span></code> does not).</p></li>
</ul>
<p>Those are big wins. Those are <em>really</em> big wins.</p>
<p>And even in the cases where C++17 could solve the problem just fine, writing constraints with <code class="sourceCode cpp"><span class="kw">concept</span></code>s and <code class="sourceCode cpp"><span class="kw">requires</span></code> is just a lot nicer looking that writing constraints with <code class="sourceCode cpp">std<span class="op">::</span>enable_if</code>.</p>
<p>But there are many problems in the world of generic programming that are not simply constraining overload sets - and C++20 Concepts does not solve them. But they’re such closely related problems, that perhaps a future incarnation of them should. I’m going to go through a few such problems: <a href="#associated-types">associated types</a>, <a href="#explicit-opt-inopt-out">explicit opt-in/opt-out</a>, <a href="#customization">customization</a>, and <a href="#type-erasure">type erasure</a>.</p>
<p>I also want to make something clear up front. Many of the examples in this paper come from Ranges, so it might be easy to conclude from this that I consider Ranges to be some overly complex mess. This conclusion is the furthest thing from the truth. I use Ranges as examples precisely because I consider Ranges to be the most complete, well thought out, and generally best possible use of concepts there is. This paper exists because I do not know if it is possible to do better with the language tools that we have.</p>
<h1 id="associated-types" style="border-bottom:1px solid #cccccc"><span class="header-section-number">2</span> Associated Types<a href="#associated-types" class="self-link"></a></h1>
<p>A C++20 <code class="sourceCode cpp"><span class="kw">concept</span></code> is a predicate on types (or values or templates, but let’s just say types for simplicity). It simply provides a yes or no answer to a question. For many concepts, that is completely sufficient. Some type <code class="sourceCode cpp">T</code> either models <code class="sourceCode cpp">std<span class="op">::</span>equality_comparable</code> or it does not - there’s no other relevant information in that question. It’s easy to come up with many examples like this.</p>
<p>However, for certain concepts, a yes/no really isn’t enough. There’s more information that you need to have. Take a <code class="sourceCode cpp"><span class="kw">concept</span></code> like <code class="sourceCode cpp">std<span class="op">::</span>invocable</code>. We can say that some type <code class="sourceCode cpp">F</code> models <code class="sourceCode cpp">std<span class="op">::</span>invocable<span class="op"><</span><span class="dt">int</span><span class="op">></span></code> or not - that tells us if we can call it with <code class="sourceCode cpp"><span class="dv">42</span></code>, or not. But there’s one especially useful piece of information to have in addition to this. It’s not just: <em>can</em> I call this thing with <code class="sourceCode cpp"><span class="dv">42</span></code>. There’s also: what do I get when I do? What is the resulting type of this invocation? We call this result type an <em>associated type</em> of the concept <code class="sourceCode cpp">invocable</code>.</p>
<p>It’s really rare to want to constrain on an invocable type but not care at all about what the result of that invocation is. Typically, we either need to add further constraints on the result type or we need to take the result of the invocation and do something with it.</p>
<p>For instance, the concept <code class="sourceCode cpp">std<span class="op">::</span>predicate</code> is a refinement of <code class="sourceCode cpp">std<span class="op">::</span>invocable</code> such that the result type of that invocation models <code class="sourceCode cpp">std<span class="op">::</span>convertible_to<span class="op"><</span><span class="dt">bool</span><span class="op">></span></code>.<a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref"><sup>1</sup></a> How do we check that? We have to use a type trait:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb1-1"><a href="#cb1-1"></a><span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> F, <span class="kw">typename</span><span class="op">...</span> Args<span class="op">></span></span>
<span id="cb1-2"><a href="#cb1-2"></a> <span class="kw">concept</span> predicate <span class="op">=</span> std<span class="op">::</span>invocable<span class="op"><</span>F, Args<span class="op">...></span> <span class="op">&&</span></span>
<span id="cb1-3"><a href="#cb1-3"></a> std<span class="op">::</span>convertible_to<span class="op"><</span>std<span class="op">::</span>invoke_result_t<span class="op"><</span>F, Args<span class="op">...></span>, <span class="dt">bool</span><span class="op">></span>;</span></code></pre></div>
<p>Now here’s the question: what is the relationship between the <code class="sourceCode cpp"><span class="kw">concept</span></code> <code class="sourceCode cpp">std<span class="op">::</span>invocable</code> and the type trait <code class="sourceCode cpp">std<span class="op">::</span>invoke_result_t</code>? None. There is no relationship. How did I know the correct type trait to use in this situation? I just did. It’s just something I had to know.</p>
<p>Some readers might quibble at this point that this isn’t a real problem - after all, I introduced this as wanting to know the “result type” of “invocable”, so perhaps it’s not at all surprising that this thing is spelled <code class="sourceCode cpp">invoke_result_t</code>. But we typically want to have closely associated entities actually be more closely associated than simply having similar names. These two aren’t even in the same header.</p>
<p>Let’s take a different example. Another marquee C++20 feature is the introduction of Ranges. While <code class="sourceCode cpp">std<span class="op">::</span>invocable</code> has one associated type (even if we cannot express that association in the language), the core concept of Ranges - <code class="sourceCode cpp">std<span class="op">::</span>range</code> - has several:</p>
<ul>
<li>the iterator type</li>
<li>the sentinel type (not necessarily the same type as the iterator type)</li>
<li>the value type</li>
<li>the reference type</li>
<li>the iteration category</li>
<li>the difference type</li>
</ul>
<p>Pretty much every function template that takes a <code class="sourceCode cpp">std<span class="op">::</span>range</code> will need to use at least one of these associated types. How do we get this information today? Again, we have to rely on the use of type traits. And you just have to know what these type traits are:</p>
<ul>
<li><code class="sourceCode cpp">iterator_t</code></li>
<li><code class="sourceCode cpp">sentinel_t</code></li>
<li><code class="sourceCode cpp">range_value_t</code></li>
<li><code class="sourceCode cpp">range_reference_t</code></li>
<li><code class="sourceCode cpp">range_difference_t</code></li>
</ul>
<p>And I don’t know if there’s a type trait for the category.</p>
<p>Because we don’t have a way to express associated types, we have to solve this problem with a proliferation of type traits. Which means a much larger surface area of things people have to know in order to write any kind of code. Or worse, instead of using the type traits, people resort to reimplementing them - possibly incorrectly.</p>
<h1 id="explicit-opt-inopt-out" style="border-bottom:1px solid #cccccc"><span class="header-section-number">3</span> Explicit opt-in/opt-out<a href="#explicit-opt-inopt-out" class="self-link"></a></h1>
<p>C++20 concepts are completely implicit. But sometimes, implicit isn’t really what we want. We have <code class="sourceCode cpp"><span class="kw">explicit</span></code> for type conversions precisely because we understand that sometimes implicit conversions are good and safe and sometimes they are not. Type adherence to a concept is really no different. There are many cases where a type might fit the <em>syntactic</em> requirements of a concept but we don’t have a way of checking that it meets the <em>semantic</em> requirements of a concept, and those semantics might be important enough to merit explicit action by the user.</p>
<p>One way to allow explicit control in concept definitions is to defer to type traits. For instance, the <code class="sourceCode cpp">view</code>, <code class="sourceCode cpp">sized_range</code>, and <code class="sourceCode cpp">sized_sentinel_for</code> concepts in the standard library come with type traits that allow for explicit tuning:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb2-1"><a href="#cb2-1"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span></span>
<span id="cb2-2"><a href="#cb2-2"></a> <span class="kw">concept</span> view <span class="op">=</span></span>
<span id="cb2-3"><a href="#cb2-3"></a> range<span class="op"><</span>T<span class="op">></span> <span class="op">&&</span> semiregular<span class="op"><</span>T<span class="op">></span> <span class="op">&&</span> enable_view<span class="op"><</span>T<span class="op">></span>;</span>
<span id="cb2-4"><a href="#cb2-4"></a></span>
<span id="cb2-5"><a href="#cb2-5"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span></span>
<span id="cb2-6"><a href="#cb2-6"></a> <span class="kw">concept</span> sized_range <span class="op">=</span></span>
<span id="cb2-7"><a href="#cb2-7"></a> range<span class="op"><</span>T<span class="op">></span> <span class="op">&&</span></span>
<span id="cb2-8"><a href="#cb2-8"></a> <span class="op">!</span>disable_sized_range<span class="op"><</span>remove_cvref_t<span class="op"><</span>T<span class="op">>></span> <span class="op">&&</span></span>
<span id="cb2-9"><a href="#cb2-9"></a> <span class="kw">requires</span><span class="op">(</span>T<span class="op">&</span> t<span class="op">)</span> <span class="op">{</span> ranges<span class="op">::</span>size<span class="op">(</span>t<span class="op">)</span>; <span class="op">}</span>;</span>
<span id="cb2-10"><a href="#cb2-10"></a> </span>
<span id="cb2-11"><a href="#cb2-11"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> S, <span class="kw">class</span> I<span class="op">></span></span>
<span id="cb2-12"><a href="#cb2-12"></a> <span class="kw">concept</span> sized_sentinel_for <span class="op">=</span></span>
<span id="cb2-13"><a href="#cb2-13"></a> sentinel_for<span class="op"><</span>S, I<span class="op">></span> <span class="op">&&</span></span>
<span id="cb2-14"><a href="#cb2-14"></a> <span class="op">!</span>disable_sized_sentinel<span class="op"><</span>remove_cv_t<span class="op"><</span>S<span class="op">></span>, remove_cv_t<span class="op"><</span>I<span class="op">>></span> <span class="op">&&</span></span>
<span id="cb2-15"><a href="#cb2-15"></a> <span class="kw">requires</span><span class="op">(</span><span class="kw">const</span> I<span class="op">&</span> i, <span class="kw">const</span> S<span class="op">&</span> s<span class="op">)</span> <span class="op">{</span></span>
<span id="cb2-16"><a href="#cb2-16"></a> <span class="op">{</span> s <span class="op">-</span> i <span class="op">}</span> <span class="op">-></span> same_as<span class="op"><</span>iter_difference_t<span class="op"><</span>I<span class="op">>></span>;</span>
<span id="cb2-17"><a href="#cb2-17"></a> <span class="op">{</span> i <span class="op">-</span> s <span class="op">}</span> <span class="op">-></span> same_as<span class="op"><</span>iter_difference_t<span class="op"><</span>I<span class="op">>></span>;</span>
<span id="cb2-18"><a href="#cb2-18"></a> <span class="op">}</span></span></code></pre></div>
<p>Not all <code class="sourceCode cpp">semiregular</code> <code class="sourceCode cpp">range</code>s are <code class="sourceCode cpp">view</code>s, we need an extra knob to control. That’s what <code class="sourceCode cpp">enable_view<span class="op"><</span>T<span class="op">></span></code> is for: it’s a type trait to help opt types out of being <code class="sourceCode cpp">view</code>s. The specializations that come with the standard library help <em>exclude</em> types that provide different deep <code class="sourceCode cpp"><span class="kw">const</span></code> access (since deep <code class="sourceCode cpp"><span class="kw">const</span></code>-ness implies ownership, e.g. <code class="sourceCode cpp">std<span class="op">::</span>vector<span class="op"><</span>T<span class="op">></span></code>) and then other specific containers in the standard library that don’t provide deep <code class="sourceCode cpp"><span class="kw">const</span></code> because their only provide <code class="sourceCode cpp"><span class="kw">const</span></code> access (e.g. <code class="sourceCode cpp">std<span class="op">::</span>set<span class="op"><</span>T<span class="op">></span></code>), but also to <em>include</em> types that can opt-in directly (i.e. by way of either inheriting from <code class="sourceCode cpp">view_base</code> or otherwise specializing <code class="sourceCode cpp">enable_view</code>).</p>
<p>This ability to explicitly state which <code class="sourceCode cpp">semiregular</code> <code class="sourceCode cpp">range</code>s are and are not <code class="sourceCode cpp">view</code>s seems fundamental, but we still need a type trait for that.</p>
<p>The <code class="sourceCode cpp">sized_range</code> concept illustrates similar functionality. The semantics of <code class="sourceCode cpp">sized_range</code> are that <code class="sourceCode cpp">x<span class="op">.</span>size<span class="op">()</span></code> is <code class="sourceCode cpp">O<span class="op">(</span><span class="dv">1</span><span class="op">)</span></code>. If a <code class="sourceCode cpp">range</code> has a <code class="sourceCode cpp">size<span class="op">()</span></code> member function that is <em>not</em> constant-time, then it should opt out of being a <code class="sourceCode cpp">sized_range</code>. Pre-C++11 <code class="sourceCode cpp">std<span class="op">::</span>list</code> is one such example container. But again, we don’t have this control through the <code class="sourceCode cpp"><span class="kw">concept</span></code>, we need to come up with some external mechanism, the easiest of which is a type trait.</p>
<p>There is a another Ranges concept that requires explicit opt-in, but does so without a type trait. And that is <em><code class="sourceCode cpp">forwarding<span class="op">-</span>range</code></em>. The semantics of a <em><code class="sourceCode cpp">forwarding<span class="op">-</span>range</code></em> are that the iterators’ validity is not tied to the lifetime of the <code class="sourceCode cpp">range</code> object. This is a purely semantic constraint that is impossible to determine merely syntactically, and a semantic that would be dangerous to get wrong at that, so it’s precisely that kind of thing that merits an explicit opt-in. The design is: a (non-reference) type <code class="sourceCode cpp">R</code> satisfies <em><code class="sourceCode cpp">forwarding<span class="op">-</span>range</code></em> if there is are <em>non-member</em> <code class="sourceCode cpp">begin<span class="op">()</span></code> and <code class="sourceCode cpp">end<span class="op">()</span></code> functions that can be found by argument-dependent lookup that either take an <code class="sourceCode cpp">R</code> by value or by rvalue reference. While this mechanism is not exactly a type trait, it does provide the same function: we need an explicit opt-in mechanism for a <code class="sourceCode cpp"><span class="kw">concept</span></code>.</p>
<p>Because we don’t have a way to express explicit opt-in or opt-out, we have to solve this problem with either a proliferation of type traits or more bespoke solutions. Which again means a much larger surface area of things people have to know in order to write any kind of code.</p>
<h2 id="opting-into-customization"><span class="header-section-number">3.1</span> Opting into customization<a href="#opting-into-customization" class="self-link"></a></h2>
<p>This section largely dealt with the problem of being explicit with regards to opting into and out of a concept, as a whole. How do we opt <code class="sourceCode cpp">vector</code> and <code class="sourceCode cpp">set</code> out of <code class="sourceCode cpp">view</code>? How do we opt <code class="sourceCode cpp">subrange</code> and <code class="sourceCode cpp">string_view</code> into <em><code class="sourceCode cpp">forwarding<span class="op">-</span>range</code></em>?</p>
<p>But there’s also a different kind of opting into concepts to consider: how do we actually opt into <code class="sourceCode cpp">std<span class="op">::</span>range</code>? The next section will talk about the <a href="#customization">customization</a> problem as a whole, but let’s just focus on the opt-in. In order for a type to be a <code class="sourceCode cpp">range</code>, it needs to have <code class="sourceCode cpp">begin<span class="op">()</span></code> and <code class="sourceCode cpp">end<span class="op">()</span></code> functions (member or non-member) that return an iterator/sentinel pair. That, in of itself, is well understood:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb3-1"><a href="#cb3-1"></a><span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> T<span class="op">></span></span>
<span id="cb3-2"><a href="#cb3-2"></a><span class="kw">struct</span> my_vector <span class="op">{</span></span>
<span id="cb3-3"><a href="#cb3-3"></a> <span class="co">// ...</span></span>
<span id="cb3-4"><a href="#cb3-4"></a> </span>
<span id="cb3-5"><a href="#cb3-5"></a> <span class="kw">auto</span> begin<span class="op">()</span> <span class="op">-></span> T<span class="op">*</span>;</span>
<span id="cb3-6"><a href="#cb3-6"></a> <span class="kw">auto</span> end<span class="op">()</span> <span class="op">-></span> T<span class="op">*</span>;</span>
<span id="cb3-7"><a href="#cb3-7"></a> </span>
<span id="cb3-8"><a href="#cb3-8"></a> <span class="kw">auto</span> begin<span class="op">()</span> <span class="kw">const</span> <span class="op">-></span> T <span class="kw">const</span><span class="op">*</span>;</span>
<span id="cb3-9"><a href="#cb3-9"></a> <span class="kw">auto</span> end<span class="op">()</span> <span class="kw">const</span> <span class="op">-></span> T <span class="kw">const</span><span class="op">*</span>;</span>
<span id="cb3-10"><a href="#cb3-10"></a><span class="op">}</span>;</span></code></pre></div>
<p>But if you think about it, why are those member functions there at all? They are there precisely for the purpose of explicitly opting into what is now the <code class="sourceCode cpp">std<span class="op">::</span>range</code> concept. Your type is never <em>accidentally</em> a range, it is always on purpose. The first <code class="sourceCode cpp">begin</code>/<code class="sourceCode cpp">end</code> pair exists to ensure that <code class="sourceCode cpp">my_vector<span class="op"><</span>T<span class="op">></span></code> is a <code class="sourceCode cpp">std<span class="op">::</span>range</code> and the second <code class="sourceCode cpp">begin</code>/<code class="sourceCode cpp">end</code> pair exists to ensure that <code class="sourceCode cpp">my_vector<span class="op"><</span>T<span class="op">></span> <span class="kw">const</span></code> is a <code class="sourceCode cpp">std<span class="op">::</span>range</code>. But there’s nothing in the actual code that indicates this relationship at all.</p>
<p>Now you might think that this desire for explicitness is a bit silly at best or verbose at worst. But that’s mostly because this example is so well-known. Everybody understands ranges. But what if I added:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb4-1"><a href="#cb4-1"></a><span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> T<span class="op">></span></span>
<span id="cb4-2"><a href="#cb4-2"></a><span class="kw">struct</span> my_vector <span class="op">{</span> <span class="co">/* ... */</span> <span class="op">}</span>;</span>
<span id="cb4-3"><a href="#cb4-3"></a></span>
<span id="cb4-4"><a href="#cb4-4"></a><span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> T<span class="op">></span></span>
<span id="cb4-5"><a href="#cb4-5"></a><span class="dt">void</span> draw<span class="op">(</span>my_vector<span class="op"><</span>T<span class="op">></span> <span class="kw">const</span><span class="op">&</span>, std<span class="op">::</span>ostream<span class="op">&</span>, <span class="dt">size_t</span><span class="op">)</span>;</span></code></pre></div>
<p>What is that function doing there? Is it just some non-member function that exists in a vacuum for an application, or is there for some other purpose? Its actual purpose is to satisfy the drawable concept from Sean Parent’s “Inheritance is the Base Class of Evil” talk <span class="citation" data-cites="Parent">[<a href="#ref-Parent" role="doc-biblioref">Parent</a>]</span>. That was the intent of writing it but there’s nothing I can write to indicate that the intent of this function is to provide an implementation for that concept (outside of a comment, but nothing with actual semantics), and there’s nothing that can check that I did it correctly (was the third argument <code class="sourceCode cpp"><span class="dt">size_t</span></code> or was it <code class="sourceCode cpp"><span class="dt">int</span></code>?).</p>
<p>For this specific issue, see also Matt Calabrese’s <span class="citation" data-cites="P1292R0">[<a href="#ref-P1292R0" role="doc-biblioref">P1292R0</a>]</span> which does provide a way for a semantic override for a function like this, although it too is separate from the <code class="sourceCode cpp"><span class="kw">concept</span></code> langauge feature.</p>
<h1 id="customization" style="border-bottom:1px solid #cccccc"><span class="header-section-number">4</span> Customization<a href="#customization" class="self-link"></a></h1>
<p>Let’s got back to <code class="sourceCode cpp">std<span class="op">::</span>range</code>. How do we learn how to opt into <code class="sourceCode cpp">std<span class="op">::</span>range</code>? The definition of that concept is:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb5-1"><a href="#cb5-1"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span></span>
<span id="cb5-2"><a href="#cb5-2"></a> <span class="kw">concept</span> <em>range-impl</em> <span class="op">=</span></span>
<span id="cb5-3"><a href="#cb5-3"></a> <span class="kw">requires</span><span class="op">(</span>T<span class="op">&&</span> t<span class="op">)</span> <span class="op">{</span></span>
<span id="cb5-4"><a href="#cb5-4"></a> ranges<span class="op">::</span>begin<span class="op">(</span>std<span class="op">::</span>forward<span class="op"><</span>T<span class="op">>(</span>t<span class="op">))</span>;</span>
<span id="cb5-5"><a href="#cb5-5"></a> ranges<span class="op">::</span>end<span class="op">(</span>std<span class="op">::</span>forward<span class="op"><</span>T<span class="op">>(</span>t<span class="op">))</span>;</span>
<span id="cb5-6"><a href="#cb5-6"></a> <span class="op">}</span>;</span>
<span id="cb5-7"><a href="#cb5-7"></a></span>
<span id="cb5-8"><a href="#cb5-8"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span></span>
<span id="cb5-9"><a href="#cb5-9"></a> <span class="kw">concept</span> range <span class="op">=</span> <em>range-impl</em><span class="op"><</span>T<span class="op">&></span>;</span></code></pre></div>
<p>What does this concept definition tell you about what the interface of <code class="sourceCode cpp">T</code> has to be in order to satisfy <code class="sourceCode cpp">std<span class="op">::</span>range</code>? It doesn’t really tell you all that much at all.</p>
<p>The constraints on <code class="sourceCode cpp">T</code> aren’t in the definition of the concept <code class="sourceCode cpp">std<span class="op">::</span>range</code>. In order to to determine if <code class="sourceCode cpp">std<span class="op">::</span>range</code> is satisfied, you have to go look for what <code class="sourceCode cpp">ranges<span class="op">::</span>begin</code> and <code class="sourceCode cpp">ranges<span class="op">::</span>end</code> are and see what their constraints are. How easy is that to do? Let’s take a look at the implementation of <code class="sourceCode cpp">begin</code> in <span class="citation" data-cites="cmcstl2">[<a href="#ref-cmcstl2" role="doc-biblioref">cmcstl2</a>]</span> (the version for <code class="sourceCode cpp">end</code> is roughly the same so I’ll simply focus the dicussion on <code class="sourceCode cpp">begin</code>):</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb6-1"><a href="#cb6-1"></a><span class="kw">namespace</span> __begin <span class="op">{</span></span>
<span id="cb6-2"><a href="#cb6-2"></a> <span class="co">// Poison pill for std::begin. (See the detailed discussion at</span></span>
<span id="cb6-3"><a href="#cb6-3"></a> <span class="co">// https://github.com/ericniebler/stl2/issues/139)</span></span>
<span id="cb6-4"><a href="#cb6-4"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span> <span class="dt">void</span> begin<span class="op">(</span>T<span class="op">&&)</span> <span class="op">=</span> <span class="kw">delete</span>;</span>
<span id="cb6-5"><a href="#cb6-5"></a></span>
<span id="cb6-6"><a href="#cb6-6"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> T<span class="op">></span></span>
<span id="cb6-7"><a href="#cb6-7"></a> <span class="dt">void</span> begin<span class="op">(</span>std<span class="op">::</span>initializer_list<span class="op"><</span>T<span class="op">>)</span> <span class="op">=</span> <span class="kw">delete</span>; <span class="co">// See LWG 3258</span></span>
<span id="cb6-8"><a href="#cb6-8"></a></span>
<span id="cb6-9"><a href="#cb6-9"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R<span class="op">></span></span>
<span id="cb6-10"><a href="#cb6-10"></a> <span class="kw">concept</span> has_member <span class="op">=</span> std<span class="op">::</span>is_lvalue_reference_v<span class="op"><</span>R<span class="op">></span> <span class="op">&&</span></span>
<span id="cb6-11"><a href="#cb6-11"></a> <span class="kw">requires</span><span class="op">(</span>R<span class="op">&</span> r<span class="op">)</span> <span class="op">{</span></span>
<span id="cb6-12"><a href="#cb6-12"></a> r<span class="op">.</span>begin<span class="op">()</span>;</span>
<span id="cb6-13"><a href="#cb6-13"></a> <span class="op">{</span> __decay_copy<span class="op">(</span>r<span class="op">.</span>begin<span class="op">())</span> <span class="op">}</span> <span class="op">-></span> input_or_output_iterator;</span>
<span id="cb6-14"><a href="#cb6-14"></a> <span class="op">}</span>;</span>
<span id="cb6-15"><a href="#cb6-15"></a></span>
<span id="cb6-16"><a href="#cb6-16"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R<span class="op">></span></span>
<span id="cb6-17"><a href="#cb6-17"></a> <span class="kw">concept</span> has_non_member <span class="op">=</span> <span class="kw">requires</span><span class="op">(</span>R<span class="op">&&</span> r<span class="op">)</span> <span class="op">{</span></span>
<span id="cb6-18"><a href="#cb6-18"></a> begin<span class="op">(</span><span class="kw">static_cast</span><span class="op"><</span>R<span class="op">&&>(</span>r<span class="op">))</span>;</span>
<span id="cb6-19"><a href="#cb6-19"></a> <span class="op">{</span> __decay_copy<span class="op">(</span>begin<span class="op">(</span><span class="kw">static_cast</span><span class="op"><</span>R<span class="op">&&>(</span>r<span class="op">)))</span> <span class="op">}</span> <span class="op">-></span> input_or_output_iterator;</span>
<span id="cb6-20"><a href="#cb6-20"></a> <span class="op">}</span>;</span>
<span id="cb6-21"><a href="#cb6-21"></a></span>
<span id="cb6-22"><a href="#cb6-22"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span><span class="op">></span></span>
<span id="cb6-23"><a href="#cb6-23"></a> <span class="kw">inline</span> <span class="kw">constexpr</span> <span class="dt">bool</span> nothrow <span class="op">=</span> <span class="kw">false</span>;</span>
<span id="cb6-24"><a href="#cb6-24"></a> <span class="kw">template</span><span class="op"><</span>has_member R<span class="op">></span></span>
<span id="cb6-25"><a href="#cb6-25"></a> <span class="kw">inline</span> <span class="kw">constexpr</span> <span class="dt">bool</span> nothrow<span class="op"><</span>R<span class="op">></span> <span class="op">=</span> <span class="kw">noexcept</span><span class="op">(</span>std<span class="op">::</span>declval<span class="op"><</span>R<span class="op">&>().</span>begin<span class="op">())</span>;</span>
<span id="cb6-26"><a href="#cb6-26"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R<span class="op">></span></span>
<span id="cb6-27"><a href="#cb6-27"></a> <span class="kw">requires</span> <span class="op">(!</span>has_member<span class="op"><</span>R<span class="op">></span> <span class="op">&&</span> has_non_member<span class="op"><</span>R<span class="op">>)</span></span>
<span id="cb6-28"><a href="#cb6-28"></a> <span class="kw">inline</span> <span class="kw">constexpr</span> <span class="dt">bool</span> nothrow<span class="op"><</span>R<span class="op">></span> <span class="op">=</span> <span class="kw">noexcept</span><span class="op">(</span>begin<span class="op">(</span>std<span class="op">::</span>declval<span class="op"><</span>R<span class="op">>()))</span>;</span>
<span id="cb6-29"><a href="#cb6-29"></a></span>
<span id="cb6-30"><a href="#cb6-30"></a> <span class="kw">struct</span> __fn <span class="op">{</span></span>
<span id="cb6-31"><a href="#cb6-31"></a> <span class="co">// Handle builtin arrays directly</span></span>
<span id="cb6-32"><a href="#cb6-32"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R, std<span class="op">::</span><span class="dt">size_t</span> N<span class="op">></span></span>
<span id="cb6-33"><a href="#cb6-33"></a> <span class="dt">void</span> <span class="kw">operator</span><span class="op">()(</span>R <span class="op">(&&)[</span>N<span class="op">])</span> <span class="kw">const</span> <span class="op">=</span> <span class="kw">delete</span>;</span>
<span id="cb6-34"><a href="#cb6-34"></a></span>
<span id="cb6-35"><a href="#cb6-35"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R, std<span class="op">::</span><span class="dt">size_t</span> N<span class="op">></span></span>
<span id="cb6-36"><a href="#cb6-36"></a> <span class="kw">constexpr</span> R<span class="op">*</span> <span class="kw">operator</span><span class="op">()(</span>R <span class="op">(&</span>array<span class="op">)[</span>N<span class="op">])</span> <span class="kw">const</span> <span class="kw">noexcept</span> <span class="op">{</span></span>
<span id="cb6-37"><a href="#cb6-37"></a> <span class="cf">return</span> array;</span>
<span id="cb6-38"><a href="#cb6-38"></a> <span class="op">}</span></span>
<span id="cb6-39"><a href="#cb6-39"></a></span>
<span id="cb6-40"><a href="#cb6-40"></a> <span class="co">// Handle basic_string_view directly to implement P0970 non-intrusively</span></span>
<span id="cb6-41"><a href="#cb6-41"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> CharT, <span class="kw">class</span> Traits<span class="op">></span></span>
<span id="cb6-42"><a href="#cb6-42"></a> <span class="kw">constexpr</span> <span class="kw">auto</span> <span class="kw">operator</span><span class="op">()(</span></span>
<span id="cb6-43"><a href="#cb6-43"></a> std<span class="op">::</span>basic_string_view<span class="op"><</span>CharT, Traits<span class="op">></span> sv<span class="op">)</span> <span class="kw">const</span> <span class="kw">noexcept</span> <span class="op">{</span></span>
<span id="cb6-44"><a href="#cb6-44"></a> <span class="cf">return</span> sv<span class="op">.</span>begin<span class="op">()</span>;</span>
<span id="cb6-45"><a href="#cb6-45"></a> <span class="op">}</span></span>
<span id="cb6-46"><a href="#cb6-46"></a></span>
<span id="cb6-47"><a href="#cb6-47"></a> <span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R<span class="op">></span></span>
<span id="cb6-48"><a href="#cb6-48"></a> <span class="kw">requires</span> has_member<span class="op"><</span>R<span class="op">></span> <span class="op">||</span> has_non_member<span class="op"><</span>R<span class="op">></span></span>
<span id="cb6-49"><a href="#cb6-49"></a> <span class="kw">constexpr</span> <span class="kw">auto</span> <span class="kw">operator</span><span class="op">()(</span>R<span class="op">&&</span> r<span class="op">)</span> <span class="kw">const</span> <span class="kw">noexcept</span><span class="op">(</span>nothrow<span class="op"><</span>R<span class="op">>)</span> <span class="op">{</span></span>
<span id="cb6-50"><a href="#cb6-50"></a> <span class="cf">if</span> <span class="kw">constexpr</span> <span class="op">(</span>has_member<span class="op"><</span>R<span class="op">>)</span> <span class="op">{</span></span>
<span id="cb6-51"><a href="#cb6-51"></a> <span class="cf">return</span> r<span class="op">.</span>begin<span class="op">()</span>;</span>
<span id="cb6-52"><a href="#cb6-52"></a> <span class="op">}</span> <span class="cf">else</span> <span class="op">{</span></span>
<span id="cb6-53"><a href="#cb6-53"></a> <span class="cf">return</span> begin<span class="op">(</span><span class="kw">static_cast</span><span class="op"><</span>R<span class="op">&&>(</span>r<span class="op">))</span>;</span>
<span id="cb6-54"><a href="#cb6-54"></a> <span class="op">}</span></span>
<span id="cb6-55"><a href="#cb6-55"></a> <span class="op">}</span></span>
<span id="cb6-56"><a href="#cb6-56"></a> <span class="op">}</span>;</span>
<span id="cb6-57"><a href="#cb6-57"></a><span class="op">}</span></span>
<span id="cb6-58"><a href="#cb6-58"></a></span>
<span id="cb6-59"><a href="#cb6-59"></a><span class="kw">inline</span> <span class="kw">namespace</span> __cpos <span class="op">{</span></span>
<span id="cb6-60"><a href="#cb6-60"></a> <span class="kw">inline</span> <span class="kw">constexpr</span> __begin<span class="op">::</span>__fn begin<span class="op">{}</span>;</span>
<span id="cb6-61"><a href="#cb6-61"></a><span class="op">}</span></span>
<span id="cb6-62"><a href="#cb6-62"></a></span>
<span id="cb6-63"><a href="#cb6-63"></a><span class="kw">template</span><span class="op"><</span><span class="kw">class</span> R<span class="op">></span></span>
<span id="cb6-64"><a href="#cb6-64"></a><span class="kw">using</span> __begin_t <span class="op">=</span> <span class="kw">decltype</span><span class="op">(</span>begin<span class="op">(</span>std<span class="op">::</span>declval<span class="op"><</span>R<span class="op">>()))</span>;</span></code></pre></div>
<p>Unless you’ve seen this style of code before and are very familiar with the design, it’s probably going to be pretty hard to figure out what you actually need to do. Moreover, for the authors of a concept, this is a lot of fairly complex code! Using C++20 concepts makes this code substantially easier to write and understand than than the C++17 version would have been, but it’s still not exactly either easy to write or understand.</p>
<p>The important question is: why does this have to be so complex?</p>
<p>We have two sources of implementation complexity here, in my opinion:</p>
<ol type="1">
<li>In the implementation of <code class="sourceCode cpp">ranges<span class="op">::</span>begin</code>, we have the explicit opt-in for <em><code class="sourceCode cpp">forwarding<span class="op">-</span>range</code></em> mentioned earlier: the poison pill overloads, the specific overload for <code class="sourceCode cpp">basic_string_view</code> and deleted rvalue array, and the <code class="sourceCode cpp">is_lvalue_reference</code> constraint on <code class="sourceCode cpp">has_member</code>.</li>
<li>To maximize usability, we want to specify <em>what</em> a type must opt into, but not make any restrictions on <em>how</em> a type must opt into it.</li>
</ol>
<p>The first part I already discussed, so let’s talk about the second.</p>
<p>A type models <code class="sourceCode cpp">std<span class="op">::</span>range</code> if it has a <code class="sourceCode cpp">begin<span class="op">()</span></code> function that returns an iterator. The question is <em>how</em> can a type provide this <code class="sourceCode cpp">begin<span class="op">()</span></code>?</p>
<p>We don’t want to impose on class authors how their types have to model our concepts - whether member or non-member function - we want it to be up to them. This allows maximal flexibility. But whichever path a type takes, we want to be easy for authors of generic code to write that code without having to go through all this process - either the careful constraints that can be seen in the implementation of <code class="sourceCode cpp">begin</code> above, or simply adding a free function that calls the member function (as in <code class="sourceCode cpp">std<span class="op">::</span>begin</code>) and then requiring what Eric Niebler called the “Std Swap Two-Step” <span class="citation" data-cites="Niebler">[<a href="#ref-Niebler" role="doc-biblioref">Niebler</a>]</span>:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb7-1"><a href="#cb7-1"></a><span class="kw">using</span> std<span class="op">::</span>begin;</span>
<span id="cb7-2"><a href="#cb7-2"></a>begin<span class="op">(</span>x<span class="op">)</span>;</span></code></pre></div>
<p>A this point, you might be thinking that the solution that I’m thinking of for this problem is unified function call syntax. But UFCS would not actually solve this problem,<a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref"><sup>2</sup></a> we need something else.</p>
<p>As a result, if we want to give people flexibility in how they can opt into concepts (which of course we do), then we cannot even specify our constraints within concepts themselves. We have to defer to function objects with pairs of concepts to handle both member and non-member implementations. None of the code is reusable. We have a fairly simple concept (we’re just checking for two functions whose return types have to satisfy other concepts, this isn’t, in of itself, especially complex), yet this still takes about 140 lines of code in Casey Carter’s implementation.</p>
<p>But customization is a critical piece of generic programming. This seems like something that should be handled by a concepts language feature. The status quo just seems like too much code, that is too complicated and too easy to mess up, to have to write for each and every concept.</p>
<p>Because we don’t have a way to directly express customization with concepts, we have to solve this problem with a proliferation of function objects. Which means a much larger surface area of things people have to know in order to write any kind of code. Or worse, instead of using the function objects, people will choose a syntax - leading to under-constrained templates.<a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref"><sup>3</sup></a></p>
<h1 id="type-erasure" style="border-bottom:1px solid #cccccc"><span class="header-section-number">5</span> Type Erasure<a href="#type-erasure" class="self-link"></a></h1>
<p>The three earlier problems presented are issues with using <code class="sourceCode cpp"><span class="kw">concept</span></code>s directly - opting in or out, getting more information, being explicit, using them in generic code. An entirely different kind of problem is: how can we use a <code class="sourceCode cpp"><span class="kw">concept</span></code> to build something else out of it? In the same Sean Parent talk I cited earlier <span class="citation" data-cites="Parent">[<a href="#ref-Parent" role="doc-biblioref">Parent</a>]</span>, he presents an argument against the idea of polymorphic types. To quote some lines from his slides:</p>
<blockquote>
<p>There are no polymorphic types, only a <em>polymorphic use</em> of similar types</p>
</blockquote>
<blockquote>
<p>By using inheritance to capture polymorphic use, we shift the burden of use to the type implementation, tightly coupling components</p>
</blockquote>
<blockquote>
<p>Inheritance implies variable size, which implies heap allocation</p>
</blockquote>
<blockquote>
<p>Heap allocation forces a further burden to manage the object lifetime</p>
</blockquote>
<blockquote>
<p>Indirection, heap allocation, virtualization impacts performance</p>
</blockquote>
<p>He then goes on to present a type erasure approach to polymorphic use. This type erasure approach is built on a concept. Not a C++20 language <code class="sourceCode cpp"><span class="kw">concept</span></code>, but a concept nevertheless. It is even called concept in the slides:</p>
<div class="sourceCode" id="cb10"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb10-1"><a href="#cb10-1"></a><span class="kw">struct</span> concept_t <span class="op">{</span></span>
<span id="cb10-2"><a href="#cb10-2"></a> <span class="kw">virtual</span> <span class="op">~</span>concept_t<span class="op">()</span> <span class="op">=</span> <span class="cf">default</span>;</span>
<span id="cb10-3"><a href="#cb10-3"></a> <span class="kw">virtual</span> concept_t<span class="op">*</span> copy_<span class="op">()</span> <span class="kw">const</span> <span class="op">=</span> <span class="dv">0</span>;</span>
<span id="cb10-4"><a href="#cb10-4"></a> <span class="kw">virtual</span> <span class="dt">void</span> draw_<span class="op">(</span>ostream<span class="op">&</span>, <span class="dt">size_t</span><span class="op">)</span> <span class="kw">const</span> <span class="op">=</span> <span class="dv">0</span>;</span>
<span id="cb10-5"><a href="#cb10-5"></a><span class="op">}</span>;</span></code></pre></div>
<p>Can we do something like this using C++20 language concepts? The language <code class="sourceCode cpp"><span class="kw">concept</span></code> might look like this:</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb11-1"><a href="#cb11-1"></a><span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> T<span class="op">></span></span>
<span id="cb11-2"><a href="#cb11-2"></a><span class="kw">concept</span> drawable <span class="op">=</span></span>
<span id="cb11-3"><a href="#cb11-3"></a> <span class="kw">requires</span> <span class="op">(</span>T <span class="kw">const</span><span class="op">&</span> v, ostream<span class="op">&</span> os, <span class="dt">size_t</span> pos<span class="op">)</span> <span class="op">{</span></span>
<span id="cb11-4"><a href="#cb11-4"></a> parent<span class="op">::</span>draw<span class="op">(</span>v, os, pos<span class="op">)</span>; <span class="co">// a CPO for member or non-member draw</span></span>
<span id="cb11-5"><a href="#cb11-5"></a> <span class="op">}</span>;</span></code></pre></div>
<p>How do we produce a type out of this <code class="sourceCode cpp"><span class="kw">concept</span></code> which can hold any <code class="sourceCode cpp">drawable</code> that is also itself <code class="sourceCode cpp">drawable</code>? Even with full reflection facilities, this seems like an overwhelmingly difficult problem. It’s telling that all the reflection-based type erasure work has not been based on <code class="sourceCode cpp"><span class="kw">concept</span></code>s but has been instead based on simple class definitions with member functions (Louis Dionne presented such an idea at CppCon 2017 <span class="citation" data-cites="Dionne">[<a href="#ref-Dionne" role="doc-biblioref">Dionne</a>]</span>, Sy Brand implemented this recently using metaclasses <span class="citation" data-cites="Brand">[<a href="#ref-Brand" role="doc-biblioref">Brand</a>]</span> <span class="citation" data-cites="Brand.Github">[<a href="#ref-Brand.Github" role="doc-biblioref">Brand.Github</a>]</span>, and Andrew Sutton discussed and heavily praised Sy’s implementation at CppCon 2019 <span class="citation" data-cites="Sutton">[<a href="#ref-Sutton" role="doc-biblioref">Sutton</a>]</span>).</p>
<p>Such a generalized facility, to take one or more <code class="sourceCode cpp"><span class="kw">concept</span></code>s and synthesized a type erased object out of them so that they do not need to be hand-written, would be incredibly useful. We even have a ready-made case study. C++11 added <code class="sourceCode cpp">std<span class="op">::</span>function</code>, a type erased, copyable, owning callable. This type has proven very useful. But for C++20, we tried to add two more very similar types:</p>
<ul>
<li>A type-erased, move-only, owning callable: <code class="sourceCode cpp">std<span class="op">::</span>any_invocable</code> <span class="citation" data-cites="P0288R4">[<a href="#ref-P0288R4" role="doc-biblioref">P0288R4</a>]</span></li>
<li>A type-erased, non-owning callable: <code class="sourceCode cpp">std<span class="op">::</span>function_ref</code> <span class="citation" data-cites="P0792R4">[<a href="#ref-P0792R4" role="doc-biblioref">P0792R4</a>]</span></li>
</ul>
<p>If we had the ability to take a <code class="sourceCode cpp"><span class="kw">concept</span></code> and create a type erased type out of it, all of this work would have been trivial. The papers in question would have either just been requests to add alias templates (if we would even need such to begin with):</p>
<div>
<div class="sourceCode" id="cb12"><pre class="sourceCode diff"><code class="sourceCode diff"><span id="cb12-1"><a href="#cb12-1"></a> namespace std {</span>
<span id="cb12-2"><a href="#cb12-2"></a> template <typename Sig></span>
<span id="cb12-3"><a href="#cb12-3"></a> using function = any_concept<invocable<Sig>, sbo_storage<<em>implementation-defined</em>>>;</span>
<span id="cb12-4"><a href="#cb12-4"></a></span>
<span id="cb12-5"><a href="#cb12-5"></a><span class="va">+ template <typename Sig></span></span>
<span id="cb12-6"><a href="#cb12-6"></a><span class="va">+ using any_invocable = any_concept<invocable<Sig>, move_only_storage>;</span></span>
<span id="cb12-7"><a href="#cb12-7"></a><span class="va">+ </span></span>
<span id="cb12-8"><a href="#cb12-8"></a><span class="va">+ template <typename Sig></span></span>
<span id="cb12-9"><a href="#cb12-9"></a><span class="va">+ using function_ref = any_concept<invocable<Sig>, non_owning_storage>;</span></span>
<span id="cb12-10"><a href="#cb12-10"></a> }</span></code></pre></div>
</div>
<p>Concept-driven type erasure is an important use case of <code class="sourceCode cpp"><span class="kw">concept</span></code>s, one which isn’t solved by the language feature we have today. Instead, we have to solve this with a proliferation of types which hand-implement the specific type erasure with the specific storage choice on a case-by-case basis. Because these types are so difficult to write, yet so useful, there is a push to add them to the standard library – and each such type is an independent, slow process.</p>
<p>Potentially, with a future generative metaprogramming language feature, built on <span class="citation" data-cites="P0707R4">[<a href="#ref-P0707R4" role="doc-biblioref">P0707R4</a>]</span> and <span class="citation" data-cites="P1717R0">[<a href="#ref-P1717R0" role="doc-biblioref">P1717R0</a>]</span>, we could write a library to avoid hand-implementing type erased objects (as in Sy’s example <span class="citation" data-cites="Brand.Github">[<a href="#ref-Brand.Github" role="doc-biblioref">Brand.Github</a>]</span>). It’s just that such a library would not be based on <code class="sourceCode cpp"><span class="kw">concept</span></code>s, and would either lead to a bifurcation of the contraint system or we would have such a library would inject a <code class="sourceCode cpp"><span class="kw">concept</span></code>s for us. Either of which seems like an inadequacy of <code class="sourceCode cpp"><span class="kw">concept</span></code>s.</p>
<h1 id="proposal" style="border-bottom:1px solid #cccccc"><span class="header-section-number">6</span> Proposal<a href="#proposal" class="self-link"></a></h1>
<p>As I said in the very beginning of this paper, this paper is not a proposal. I do not have concrete suggestions for how to solve any of these problems (or even vaguely amorphous suggestions). The goal of this paper is instead to present the problems that the concepts language feature could solve, and should solve, but at the moment does not.</p>
<p>But because these problems have to be solved, we end up with proliferations of type traits, bespoke opt-in solutions, customization point objects, and whole classes. The surface area that a programmer needs to know to write good generic code is enormous.</p>
<p>To the extent that that this paper is a proposal, it’s a proposal for proposals to solve these problems and a proposal to seriously consider those future proposals. This might mean restarting SG8, or simply taking more EWG time. But they’re big problems and solving them could reap huge benefits.</p>
<h1 id="references" style="border-bottom:1px solid #cccccc"><span class="header-section-number">7</span> References<a href="#references" class="self-link"></a></h1>
<div id="refs" role="doc-bibliography">
<div id="ref-Brand">
<p>[Brand] Sy Brand. 2019. I’ve written a proof-of-concept implementation of Rust-style trait objects in C++ using the experimental metaclasses compiler. <br />
<a href="https://twitter.com/tartanllama/status/1159445548417634324?lang=en">https://twitter.com/tartanllama/status/1159445548417634324?lang=en</a></p>
</div>
<div id="ref-Brand.Github">
<p>[Brand.Github] Sy Brand. 2019. Typeclasses in C++. <br />
<a href="https://github.com/tartanllama/typeclasses/">https://github.com/tartanllama/typeclasses/</a></p>
</div>
<div id="ref-cmcstl2">
<p>[cmcstl2] Casey Carter. 2019. An implementation of C++ Extensions for Ranges. <br />
<a href="https://github.com/CaseyCarter/cmcstl2/blob/43c77f9152c2470f8bc4f820f88ef51639ac2053/include/stl2/detail/range/access.hpp#L41-L100">https://github.com/CaseyCarter/cmcstl2/blob/43c77f9152c2470f8bc4f820f88ef51639ac2053/include/stl2/detail/range/access.hpp#L41-L100</a></p>
</div>
<div id="ref-Dionne">
<p>[Dionne] Louis Dionne. 2013. CppCon 2017: Runtime Polymorphism: Back to the Basics. <br />
<a href="https://youtu.be/gVGtNFg4ay0?t=3242">https://youtu.be/gVGtNFg4ay0?t=3242</a></p>
</div>
<div id="ref-Niebler">
<p>[Niebler] Eric Niebler. 2014. Customization Point Design in C++11 and Beyond. <br />
<a href="http://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/">http://ericniebler.com/2014/10/21/customization-point-design-in-c11-and-beyond/</a></p>
</div>
<div id="ref-P0288R4">
<p>[P0288R4] Ryan McDougall, Matt Calabrese. 2019. any_invocable. <br />
<a href="https://wg21.link/p0288r4">https://wg21.link/p0288r4</a></p>
</div>
<div id="ref-P0707R4">
<p>[P0707R4] Herb Sutter. 2019. Metaclasses: Generative C++. <br />
<a href="https://wg21.link/p0707r4">https://wg21.link/p0707r4</a></p>
</div>
<div id="ref-P0792R4">
<p>[P0792R4] Vittorio Romeo. 2019. function_ref: a non-owning reference to a Callable. <br />
<a href="https://wg21.link/p0792r4">https://wg21.link/p0792r4</a></p>
</div>
<div id="ref-P1292R0">
<p>[P1292R0] Matt Calabrese. 2018. Customization Point Functions. <br />
<a href="https://wg21.link/p1292r0">https://wg21.link/p1292r0</a></p>
</div>
<div id="ref-P1717R0">
<p>[P1717R0] Andrew Sutton, Wyatt Childers. 2019. Compile-time Metaprogramming in C++. <br />
<a href="https://wg21.link/p1717r0">https://wg21.link/p1717r0</a></p>
</div>
<div id="ref-Parent">
<p>[Parent] Sean Parent. 2013. GoingNative 2013: Inheritance Is The Base Class of Evil. <br />
<a href="https://www.youtube.com/watch?v=2bLkxj6EVoM">https://www.youtube.com/watch?v=2bLkxj6EVoM</a></p>
</div>
<div id="ref-Sutton">
<p>[Sutton] Andrew Sutton. 2019. Meta++: Language Support for Advanced Generative Programming. <br />
<a href="https://youtu.be/kjQXhuPX-Ac?t=2057">https://youtu.be/kjQXhuPX-Ac?t=2057</a></p>
</div>
</div>
<section class="footnotes" role="doc-endnotes">
<hr />
<ol>
<li id="fn1" role="doc-endnote"><p>This is not the current definition of <code class="sourceCode cpp">std<span class="op">::</span>predicate</code>, but possibly should be, and in any case, the difference isn’t relevant for this paper.<a href="#fnref1" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn2" role="doc-endnote"><p>Let’s consider the version of UFCS that said that member functions can find non-member functions. What would this mean:</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb8-1"><a href="#cb8-1"></a><span class="dt">int</span> arr<span class="op">[</span><span class="dv">10</span><span class="op">]</span>;</span>
<span id="cb8-2"><a href="#cb8-2"></a>arr<span class="op">.</span>begin<span class="op">()</span>;</span></code></pre></div>
<p>Arrays do not have member functions, so we try to find a <code class="sourceCode cpp">begin<span class="op">(</span>arr<span class="op">)</span></code>. But <code class="sourceCode cpp"><span class="dt">int</span><span class="op">[</span><span class="dv">10</span><span class="op">]</span></code> doesn’t have any associated namespaces. Such a call would only succeed if there were a <code class="sourceCode cpp">begin</code> in scope. Where would our array overload for <code class="sourceCode cpp">begin</code> live? It would have to live in global namespace? But even then, we would have to rely on there not being any other <code class="sourceCode cpp">begin</code>s between where we are and that global declaration otherwise this won’t work. To be safe, we’d have to put the array overload somewhere specific and bring it in scope:</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span id="cb9-1"><a href="#cb9-1"></a><span class="kw">namespace</span> std <span class="op">{</span></span>
<span id="cb9-2"><a href="#cb9-2"></a> <span class="kw">template</span> <span class="op"><</span><span class="kw">typename</span> T, <span class="dt">size_t</span> N<span class="op">></span></span>
<span id="cb9-3"><a href="#cb9-3"></a> <span class="kw">constexpr</span> T<span class="op">*</span> begin<span class="op">(</span>T <span class="op">(&</span>arr<span class="op">)[</span>N<span class="op">])</span> <span class="kw">noexcept</span> <span class="op">{</span> <span class="cf">return</span> arr; <span class="op">}</span></span>
<span id="cb9-4"><a href="#cb9-4"></a><span class="op">}</span></span>
<span id="cb9-5"><a href="#cb9-5"></a></span>
<span id="cb9-6"><a href="#cb9-6"></a><span class="dt">int</span> arr<span class="op">[</span><span class="dv">10</span><span class="op">]</span>;</span>
<span id="cb9-7"><a href="#cb9-7"></a><span class="kw">using</span> std<span class="op">::</span>begin;</span>
<span id="cb9-8"><a href="#cb9-8"></a>arr<span class="op">.</span>begin<span class="op">()</span>; <span class="co">// ok, would call std::begin(arr)</span></span></code></pre></div>
<p>But at this point, we’re doing the Two-Step (because we have to), so we didn’t really gain anything from UFCS. The same problem will come up anytime you want to customize a function for things like pointers, arrays, or just fundamental types.<a href="#fnref2" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
<li id="fn3" role="doc-endnote"><p>What I mean is, instead of using <code class="sourceCode cpp">ranges<span class="op">::</span>begin<span class="op">(</span>x<span class="op">)</span></code> in generic code which takes a <code class="sourceCode cpp">std<span class="op">::</span>range</code>, people will write either <code class="sourceCode cpp">x<span class="op">.</span>begin<span class="op">()</span></code> or <code class="sourceCode cpp">begin<span class="op">(</span>x<span class="op">)</span></code> – both of which are incorrect.<a href="#fnref3" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
</ol>
</section>
</div>
</div>
</body>
</html>