-
Notifications
You must be signed in to change notification settings - Fork 22
/
p0893r1.html
executable file
·828 lines (721 loc) · 54.7 KB
/
p0893r1.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
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Chaining Comparisons</title>
<style type="text/css">html {
position: relative;
max-width: 1024px;
height: 100%;
}
body {
font-family: Helvetica, arial, sans-serif;
font-size: 14px;
line-height: 1.6;
padding-top: 10px;
padding-bottom: 10px;
background-color: white;
padding: 30px;
}
body>*:first-child {
margin-top: 0 !important;
}
body>*:last-child {
margin-bottom: 0 !important;
}
a {
color: #4183C4;
}
a.absent {
color: #cc0000;
}
a.anchor {
display: block;
padding-left: 30px;
margin-left: -30px;
cursor: pointer;
position: absolute;
top: 0;
left: 0;
bottom: 0;
}
h1, h2, h3, h4, h5, h6 {
margin: 20px 0 10px;
padding: 0;
font-weight: bold;
-webkit-font-smoothing: antialiased;
cursor: text;
position: relative;
}
h1:hover a.anchor, h2:hover a.anchor, h3:hover a.anchor, h4:hover a.anchor, h5:hover a.anchor, h6:hover a.anchor {
background: url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAYAAAAf8/9hAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAA09pVFh0WE1MOmNvbS5hZG9iZS54bXAAAAAAADw/eHBhY2tldCBiZWdpbj0i77u/IiBpZD0iVzVNME1wQ2VoaUh6cmVTek5UY3prYzlkIj8+IDx4OnhtcG1ldGEgeG1sbnM6eD0iYWRvYmU6bnM6bWV0YS8iIHg6eG1wdGs9IkFkb2JlIFhNUCBDb3JlIDUuMy1jMDExIDY2LjE0NTY2MSwgMjAxMi8wMi8wNi0xNDo1NjoyNyAgICAgICAgIj4gPHJkZjpSREYgeG1sbnM6cmRmPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjIj4gPHJkZjpEZXNjcmlwdGlvbiByZGY6YWJvdXQ9IiIgeG1sbnM6eG1wPSJodHRwOi8vbnMuYWRvYmUuY29tL3hhcC8xLjAvIiB4bWxuczp4bXBNTT0iaHR0cDovL25zLmFkb2JlLmNvbS94YXAvMS4wL21tLyIgeG1sbnM6c3RSZWY9Imh0dHA6Ly9ucy5hZG9iZS5jb20veGFwLzEuMC9zVHlwZS9SZXNvdXJjZVJlZiMiIHhtcDpDcmVhdG9yVG9vbD0iQWRvYmUgUGhvdG9zaG9wIENTNiAoMTMuMCAyMDEyMDMwNS5tLjQxNSAyMDEyLzAzLzA1OjIxOjAwOjAwKSAgKE1hY2ludG9zaCkiIHhtcE1NOkluc3RhbmNlSUQ9InhtcC5paWQ6OUM2NjlDQjI4ODBGMTFFMTg1ODlEODNERDJBRjUwQTQiIHhtcE1NOkRvY3VtZW50SUQ9InhtcC5kaWQ6OUM2NjlDQjM4ODBGMTFFMTg1ODlEODNERDJBRjUwQTQiPiA8eG1wTU06RGVyaXZlZEZyb20gc3RSZWY6aW5zdGFuY2VJRD0ieG1wLmlpZDo5QzY2OUNCMDg4MEYxMUUxODU4OUQ4M0REMkFGNTBBNCIgc3RSZWY6ZG9jdW1lbnRJRD0ieG1wLmRpZDo5QzY2OUNCMTg4MEYxMUUxODU4OUQ4M0REMkFGNTBBNCIvPiA8L3JkZjpEZXNjcmlwdGlvbj4gPC9yZGY6UkRGPiA8L3g6eG1wbWV0YT4gPD94cGFja2V0IGVuZD0iciI/PsQhXeAAAABfSURBVHjaYvz//z8DJYCRUgMYQAbAMBQIAvEqkBQWXI6sHqwHiwG70TTBxGaiWwjCTGgOUgJiF1J8wMRAIUA34B4Q76HUBelAfJYSA0CuMIEaRP8wGIkGMA54bgQIMACAmkXJi0hKJQAAAABJRU5ErkJggg==) no-repeat 10px center;
text-decoration: none;
}
h1 tt, h1 code {
font-size: inherit;
}
h2 tt, h2 code {
font-size: inherit;
}
h3 tt, h3 code {
font-size: inherit;
}
h4 tt, h4 code {
font-size: inherit;
}
h5 tt, h5 code {
font-size: inherit;
}
h6 tt, h6 code {
font-size: inherit;
}
h1 {
font-size: 28px;
color: black;
}
h2 {
font-size: 24px;
border-bottom: 1px solid #cccccc;
color: black;
}
h3 {
font-size: 18px;
}
h4 {
font-size: 16px;
}
h5 {
font-size: 14px;
}
h6 {
color: #777777;
font-size: 14px;
}
p, blockquote, ol, dl, li, table, pre {
margin: 15px 0;
}
hr {
background: transparent url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAECAYAAACtBE5DAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAAyJpVFh0WE1MOmNvbS5hZG9iZS54bXAAAAAAADw/eHBhY2tldCBiZWdpbj0i77u/IiBpZD0iVzVNME1wQ2VoaUh6cmVTek5UY3prYzlkIj8+IDx4OnhtcG1ldGEgeG1sbnM6eD0iYWRvYmU6bnM6bWV0YS8iIHg6eG1wdGs9IkFkb2JlIFhNUCBDb3JlIDUuMC1jMDYwIDYxLjEzNDc3NywgMjAxMC8wMi8xMi0xNzozMjowMCAgICAgICAgIj4gPHJkZjpSREYgeG1sbnM6cmRmPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjIj4gPHJkZjpEZXNjcmlwdGlvbiByZGY6YWJvdXQ9IiIgeG1sbnM6eG1wPSJodHRwOi8vbnMuYWRvYmUuY29tL3hhcC8xLjAvIiB4bWxuczp4bXBNTT0iaHR0cDovL25zLmFkb2JlLmNvbS94YXAvMS4wL21tLyIgeG1sbnM6c3RSZWY9Imh0dHA6Ly9ucy5hZG9iZS5jb20veGFwLzEuMC9zVHlwZS9SZXNvdXJjZVJlZiMiIHhtcDpDcmVhdG9yVG9vbD0iQWRvYmUgUGhvdG9zaG9wIENTNSBNYWNpbnRvc2giIHhtcE1NOkluc3RhbmNlSUQ9InhtcC5paWQ6OENDRjNBN0E2NTZBMTFFMEI3QjRBODM4NzJDMjlGNDgiIHhtcE1NOkRvY3VtZW50SUQ9InhtcC5kaWQ6OENDRjNBN0I2NTZBMTFFMEI3QjRBODM4NzJDMjlGNDgiPiA8eG1wTU06RGVyaXZlZEZyb20gc3RSZWY6aW5zdGFuY2VJRD0ieG1wLmlpZDo4Q0NGM0E3ODY1NkExMUUwQjdCNEE4Mzg3MkMyOUY0OCIgc3RSZWY6ZG9jdW1lbnRJRD0ieG1wLmRpZDo4Q0NGM0E3OTY1NkExMUUwQjdCNEE4Mzg3MkMyOUY0OCIvPiA8L3JkZjpEZXNjcmlwdGlvbj4gPC9yZGY6UkRGPiA8L3g6eG1wbWV0YT4gPD94cGFja2V0IGVuZD0iciI/PqqezsUAAAAfSURBVHjaYmRABcYwBiM2QSA4y4hNEKYDQxAEAAIMAHNGAzhkPOlYAAAAAElFTkSuQmCC) repeat-x 0 0;
border: 0 none;
color: #cccccc;
height: 4px;
padding: 0;
}
body>h2:first-child {
margin-top: 0;
padding-top: 0;
}
body>h1:first-child {
margin-top: 0;
padding-top: 0;
}
body>h1:first-child+h2 {
margin-top: 0;
padding-top: 0;
}
body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
margin-top: 0;
padding-top: 0;
}
a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
margin-top: 0;
padding-top: 0;
}
h1 p, h2 p, h3 p, h4 p, h5 p, h6 p {
margin-top: 0;
}
li p.first {
display: inline-block;
}
li {
margin: 0;
}
ol {
padding-left: 30px;
margin: 5px;
counter-reset: item;
}
ol > li {
counter-increment: item;
}
ol ol > li {
display: block;
}
ul :first-child, ol :first-child {
margin-top: 0;
}
ul ul {
margin-left: -15px;
}
dl {
padding: 0;
}
dl dt {
font-size: 14px;
font-weight: bold;
font-style: italic;
padding: 0;
margin: 15px 0 5px;
}
dl dt:first-child {
padding: 0;
}
dl dt> :first-child {
margin-top: 0;
}
dl dt> :last-child {
margin-bottom: 0;
}
dl dd {
margin: 0 0 15px;
padding: 0 15px;
}
dl dd> :first-child {
margin-top: 0;
}
dl dd> :last-child {
margin-bottom: 0;
}
blockquote {
border-left: 4px solid #dddddd;
padding: 0 15px;
color: #777777;
}
blockquote> :first-child {
margin-top: 0;
}
blockquote> :last-child {
margin-bottom: 0;
}
table {
padding: 0;
border-collapse: collapse;
}
table tr {
border-top: 1px solid #cccccc;
background-color: white;
margin: 0;
padding: 0;
}
table tr:nth-child(2n) {
background-color: #f8f8f8;
}
table tr th {
font-weight: bold;
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px;
}
table tr td {
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px;
}
table tr th :first-child, table tr td :first-child {
margin-top: 0;
}
table tr th :last-child, table tr td :last-child {
margin-bottom: 0;
}
td {
vertical-align: top;
}
img {
max-width: 100%;
}
span.frame {
display: block;
overflow: hidden;
}
span.frame>span {
border: 1px solid #dddddd;
display: block;
float: left;
overflow: hidden;
margin: 13px 0 0;
padding: 7px;
width: auto;
}
span.frame span img {
display: block;
float: left;
}
span.frame span span {
clear: both;
color: #333333;
display: block;
padding: 5px 0 0;
}
span.align-center {
display: block;
overflow: hidden;
clear: both;
}
span.align-center>span {
display: block;
overflow: hidden;
margin: 13px auto 0;
text-align: center;
}
span.align-center span img {
margin: 0 auto;
text-align: center;
}
span.align-right {
display: block;
overflow: hidden;
clear: both;
}
span.align-right>span {
display: block;
overflow: hidden;
margin: 13px 0 0;
text-align: right;
}
span.align-right span img {
margin: 0;
text-align: right;
}
span.float-left {
display: block;
margin-right: 13px;
overflow: hidden;
float: left;
}
span.float-left span {
margin: 13px 0 0;
}
span.float-right {
display: block;
margin-left: 13px;
overflow: hidden;
float: right;
}
span.float-right>span {
display: block;
overflow: hidden;
margin: 13px auto 0;
text-align: right;
}
code, tt {
margin: 0 2px;
padding: 0 5px;
white-space: nowrap;
border: 1px solid #eaeaea;
background-color: #f8f8f8;
border-radius: 3px;
}
pre code {
margin: 0;
padding: 0;
white-space: pre;
border: none;
background: transparent;
}
.highlight pre {
background-color: #f8f8f8;
border: 1px solid #cccccc;
font-size: 13px;
line-height: 19px;
overflow: auto;
padding: 6px 10px;
border-radius: 3px;
}
pre {
background-color: #f8f8f8;
border: 1px solid #cccccc;
font-size: 13px;
line-height: 19px;
overflow: auto;
overflow-x: hidden;
overflow-y: hidden;
padding: 6px 10px;
border-radius: 3px;
}
pre code, pre tt {
background-color: transparent;
border: none;
}
sup {
font-size: 0.83em;
vertical-align: super;
line-height: 0;
}
kbd {
display: inline-block;
padding: 3px 5px;
font-size: 11px;
line-height: 10px;
color: #555;
vertical-align: middle;
background-color: #fcfcfc;
border: solid 1px #ccc;
border-bottom-color: #bbb;
border-radius: 3px;
box-shadow: inset 0 -1px 0 #bbb
}
* {
-webkit-print-color-adjust: exact;
}
ins {
color: #00A000
}
del {
color: #A00000
}
</style><style type="text/css">
/**
* prism.js default theme for JavaScript, CSS and HTML
* Based on dabblet (http://dabblet.com)
* @author Lea Verou
*/
code[class*="language-"], pre[class*="language-"] {
color: black;
background: none;
text-shadow: 0 1px white;
font-family: Consolas, Monaco, 'Andale Mono', 'Ubuntu Mono', monospace;
font-size: 11px;
text-align: left;
white-space: pre;
word-spacing: normal;
word-break: normal;
word-wrap: normal;
line-height: 1.5;
-moz-tab-size: 4;
-o-tab-size: 4;
tab-size: 4;
-webkit-hyphens: none;
-moz-hyphens: none;
-ms-hyphens: none;
hyphens: none;
}
pre[class*="language-"]::-moz-selection, pre[class*="language-"] ::-moz-selection, code[class*="language-"]::-moz-selection, code[class*="language-"] ::-moz-selection {
text-shadow: none;
background: #b3d4fc;
}
pre[class*="language-"]::selection, pre[class*="language-"] ::selection, code[class*="language-"]::selection, code[class*="language-"] ::selection {
text-shadow: none;
background: #b3d4fc;
}
@media print {
code[class*="language-"], pre[class*="language-"] {
text-shadow: none;
}
}
/* Code blocks */
pre[class*="language-"] {
padding: 1em;
margin: .5em 0;
overflow: auto;
overflow-x: hidden;
overflow-y: hidden;
}
:not(pre)>code[class*="language-"], pre[class*="language-"] {
background: #f8f8f8;
}
/* Inline code */
:not(pre)>code[class*="language-"] {
padding: .1em;
border-radius: .3em;
white-space: normal;
}
.token.comment, .token.prolog, .token.doctype, .token.cdata {
color: slategray;
}
.token.punctuation {
color: #999;
}
.namespace {
opacity: .7;
}
.token.property, .token.tag, .token.boolean, .token.number, .token.constant, .token.symbol, .token.deleted {
color: #905;
}
.token.selector, .token.attr-name, .token.string, .token.char, .token.builtin, .token.inserted {
color: #690;
}
.token.operator {
color: #a67f59;
}
.token.entity, .token.url, .language-css .token.string, .style .token.string {
color: #a67f59;
background: hsla(0, 0%, 100%, .5);
}
.token.atrule, .token.attr-value, .token.keyword {
color: #07a;
}
.token.function {
color: #DD4A68;
}
.token.regex, .token.important, .token.variable {
color: #e90;
}
.token.important, .token.bold {
font-weight: bold;
}
.token.italic {
font-style: italic;
}
.token.entity {
cursor: help;
}
</style>
<script type="text/javascript">
var _self="undefined"!=typeof window?window:"undefined"!=typeof WorkerGlobalScope&&self instanceof WorkerGlobalScope?self:{},Prism=function(){var e=/\blang(?:uage)?-(\w+)\b/i,t=0,n=_self.Prism={util:{encode:function(e){return e instanceof a?new a(e.type,n.util.encode(e.content),e.alias):"Array"===n.util.type(e)?e.map(n.util.encode):e.replace(/&/g,"&").replace(/</g,"<").replace(/\u00a0/g," ")},type:function(e){return Object.prototype.toString.call(e).match(/\[object (\w+)\]/)[1]},objId:function(e){return e.__id||Object.defineProperty(e,"__id",{value:++t}),e.__id},clone:function(e){var t=n.util.type(e);switch(t){case"Object":var a={};for(var r in e)e.hasOwnProperty(r)&&(a[r]=n.util.clone(e[r]));return a;case"Array":return e.map&&e.map(function(e){return n.util.clone(e)})}return e}},languages:{extend:function(e,t){var a=n.util.clone(n.languages[e]);for(var r in t)a[r]=t[r];return a},insertBefore:function(e,t,a,r){r=r||n.languages;var l=r[e];if(2==arguments.length){a=arguments[1];for(var i in a)a.hasOwnProperty(i)&&(l[i]=a[i]);return l}var o={};for(var s in l)if(l.hasOwnProperty(s)){if(s==t)for(var i in a)a.hasOwnProperty(i)&&(o[i]=a[i]);o[s]=l[s]}return n.languages.DFS(n.languages,function(t,n){n===r[e]&&t!=e&&(this[t]=o)}),r[e]=o},DFS:function(e,t,a,r){r=r||{};for(var l in e)e.hasOwnProperty(l)&&(t.call(e,l,e[l],a||l),"Object"!==n.util.type(e[l])||r[n.util.objId(e[l])]?"Array"!==n.util.type(e[l])||r[n.util.objId(e[l])]||(r[n.util.objId(e[l])]=!0,n.languages.DFS(e[l],t,l,r)):(r[n.util.objId(e[l])]=!0,n.languages.DFS(e[l],t,null,r)))}},plugins:{},highlightAll:function(e,t){var a={callback:t,selector:'code[class*="language-"], [class*="language-"] code, code[class*="lang-"], [class*="lang-"] code'};n.hooks.run("before-highlightall",a);for(var r,l=a.elements||document.querySelectorAll(a.selector),i=0;r=l[i++];)n.highlightElement(r,e===!0,a.callback)},highlightElement:function(t,a,r){for(var l,i,o=t;o&&!e.test(o.className);)o=o.parentNode;o&&(l=(o.className.match(e)||[,""])[1],i=n.languages[l]),t.className=t.className.replace(e,"").replace(/\s+/g," ")+" language-"+l,o=t.parentNode,/pre/i.test(o.nodeName)&&(o.className=o.className.replace(e,"").replace(/\s+/g," ")+" language-"+l);var s=t.textContent,u={element:t,language:l,grammar:i,code:s};if(!s||!i)return n.hooks.run("complete",u),void 0;if(n.hooks.run("before-highlight",u),a&&_self.Worker){var c=new Worker(n.filename);c.onmessage=function(e){u.highlightedCode=e.data,n.hooks.run("before-insert",u),u.element.innerHTML=u.highlightedCode,r&&r.call(u.element),n.hooks.run("after-highlight",u),n.hooks.run("complete",u)},c.postMessage(JSON.stringify({language:u.language,code:u.code,immediateClose:!0}))}else u.highlightedCode=n.highlight(u.code,u.grammar,u.language),n.hooks.run("before-insert",u),u.element.innerHTML=u.highlightedCode,r&&r.call(t),n.hooks.run("after-highlight",u),n.hooks.run("complete",u)},highlight:function(e,t,r){var l=n.tokenize(e,t);return a.stringify(n.util.encode(l),r)},tokenize:function(e,t){var a=n.Token,r=[e],l=t.rest;if(l){for(var i in l)t[i]=l[i];delete t.rest}e:for(var i in t)if(t.hasOwnProperty(i)&&t[i]){var o=t[i];o="Array"===n.util.type(o)?o:[o];for(var s=0;s<o.length;++s){var u=o[s],c=u.inside,g=!!u.lookbehind,h=!!u.greedy,f=0,d=u.alias;u=u.pattern||u;for(var p=0;p<r.length;p++){var m=r[p];if(r.length>e.length)break e;if(!(m instanceof a)){u.lastIndex=0;var y=u.exec(m),v=1;if(!y&&h&&p!=r.length-1){var b=r[p+1].matchedStr||r[p+1],k=m+b;if(p<r.length-2&&(k+=r[p+2].matchedStr||r[p+2]),u.lastIndex=0,y=u.exec(k),!y)continue;var w=y.index+(g?y[1].length:0);if(w>=m.length)continue;var _=y.index+y[0].length,P=m.length+b.length;if(v=3,P>=_){if(r[p+1].greedy)continue;v=2,k=k.slice(0,P)}m=k}if(y){g&&(f=y[1].length);var w=y.index+f,y=y[0].slice(f),_=w+y.length,S=m.slice(0,w),O=m.slice(_),j=[p,v];S&&j.push(S);var A=new a(i,c?n.tokenize(y,c):y,d,y,h);j.push(A),O&&j.push(O),Array.prototype.splice.apply(r,j)}}}}}return r},hooks:{all:{},add:function(e,t){var a=n.hooks.all;a[e]=a[e]||[],a[e].push(t)},run:function(e,t){var a=n.hooks.all[e];if(a&&a.length)for(var r,l=0;r=a[l++];)r(t)}}},a=n.Token=function(e,t,n,a,r){this.type=e,this.content=t,this.alias=n,this.matchedStr=a||null,this.greedy=!!r};if(a.stringify=function(e,t,r){if("string"==typeof e)return e;if("Array"===n.util.type(e))return e.map(function(n){return a.stringify(n,t,e)}).join("");var l={type:e.type,content:a.stringify(e.content,t,r),tag:"span",classes:["token",e.type],attributes:{},language:t,parent:r};if("comment"==l.type&&(l.attributes.spellcheck="true"),e.alias){var i="Array"===n.util.type(e.alias)?e.alias:[e.alias];Array.prototype.push.apply(l.classes,i)}n.hooks.run("wrap",l);var o="";for(var s in l.attributes)o+=(o?" ":"")+s+'="'+(l.attributes[s]||"")+'"';return"<"+l.tag+' class="'+l.classes.join(" ")+'" '+o+">"+l.content+"</"+l.tag+">"},!_self.document)return _self.addEventListener?(_self.addEventListener("message",function(e){var t=JSON.parse(e.data),a=t.language,r=t.code,l=t.immediateClose;_self.postMessage(n.highlight(r,n.languages[a],a)),l&&_self.close()},!1),_self.Prism):_self.Prism;var r=document.currentScript||[].slice.call(document.getElementsByTagName("script")).pop();return r&&(n.filename=r.src,document.addEventListener&&!r.hasAttribute("data-manual")&&document.addEventListener("DOMContentLoaded",n.highlightAll)),_self.Prism}();"undefined"!=typeof module&&module.exports&&(module.exports=Prism),"undefined"!=typeof global&&(global.Prism=Prism);
</script>
<script type="text/javascript">
Prism.languages.clike={comment:[{pattern:/(^|[^\\])\/\*[\w\W]*?\*\//,lookbehind:!0},{pattern:/(^|[^\\:])\/\/.*/,lookbehind:!0}],string:{pattern:/(["'])(\\(?:\r\n|[\s\S])|(?!\1)[^\\\r\n])*\1/,greedy:!0},"class-name":{pattern:/((?:\b(?:class|interface|extends|implements|trait|instanceof|new)\s+)|(?:catch\s+\())[a-z0-9_\.\\]+/i,lookbehind:!0,inside:{punctuation:/(\.|\\)/}},keyword:/\b(if|else|while|do|for|return|in|instanceof|function|new|try|throw|catch|finally|null|break|continue)\b/,"boolean":/\b(true|false)\b/,"function":/[a-z0-9_]+(?=\()/i,number:/\b-?(?:0x[\da-f]+|\d*\.?\d+(?:e[+-]?\d+)?)\b/i,operator:/--?|\+\+?|!=?=?|<=?|>=?|==?=?|&&?|\|\|?|\?|\*|\/|~|\^|%/,punctuation:/[{}[\];(),.:]/};
</script>
<script type="text/javascript">
Prism.languages.c=Prism.languages.extend("clike",{keyword:/\b(asm|typeof|inline|auto|break|case|char|const|continue|default|do|double|else|enum|extern|float|for|goto|if|int|long|register|return|short|signed|sizeof|static|struct|switch|typedef|union|unsigned|void|volatile|while)\b/,operator:/\-[>-]?|\+\+?|!=?|<<?=?|>>?=?|==?|&&?|\|?\||[~^%?*\/]/,number:/\b-?(?:0x[\da-f]+|\d*\.?\d+(?:e[+-]?\d+)?)[ful]*\b/i}),Prism.languages.insertBefore("c","string",{macro:{pattern:/(^\s*)#\s*[a-z]+([^\r\n\\]|\\.|\\(?:\r\n?|\n))*/im,lookbehind:!0,alias:"property",inside:{string:{pattern:/(#\s*include\s*)(<.+?>|("|')(\\?.)+?\3)/,lookbehind:!0},directive:{pattern:/(#\s*)\b(define|elif|else|endif|error|ifdef|ifndef|if|import|include|line|pragma|undef|using)\b/,lookbehind:!0,alias:"keyword"}}},constant:/\b(__FILE__|__LINE__|__DATE__|__TIME__|__TIMESTAMP__|__func__|EOF|NULL|stdin|stdout|stderr)\b/}),delete Prism.languages.c["class-name"],delete Prism.languages.c["boolean"];
</script>
<script type="text/javascript">
Prism.languages.cpp=Prism.languages.extend("c",{keyword:/\b(alignas|alignof|asm|auto|bool|break|case|catch|char|char16_t|char32_t|class|compl|const|constexpr|const_cast|continue|decltype|default|delete|do|double|dynamic_cast|else|enum|explicit|export|extern|float|for|friend|goto|if|inline|int|long|mutable|namespace|new|noexcept|nullptr|operator|private|protected|public|register|reinterpret_cast|requires|return|short|signed|sizeof|static|static_assert|static_cast|struct|switch|template|this|thread_local|throw|try|typedef|typeid|typename|union|unsigned|using|virtual|void|volatile|wchar_t|while)\b/,"boolean":/\b(true|false)\b/,operator:/[-+]{1,2}|!=?|<{1,2}=?|>{1,2}=?|\->|:{1,2}|={1,2}|\^|~|%|&{1,2}|\|?\||\?|\*|\/|\b(and|and_eq|bitand|bitor|not|not_eq|or|or_eq|xor|xor_eq)\b/}),Prism.languages.insertBefore("cpp","keyword",{"class-name":{pattern:/(class\s+)[a-z0-9_]+/i,lookbehind:!0}});
</script>
</head>
<body>
<address align=right>
Document number: P0893R1 <br />
Date: 2018-04-28 <br />
Audience: Evolution Working Group <br />
Reply-To: Barry Revzin <[email protected]> <br />
Herb Sutter <[email protected]>
</address>
<hr/>
<h1 align=center>Chaining Comparisons</h1>
<h2>Contents</h2>
<ul>
<li><a href="#Revisions">Revision History</a></li>
<li><a href="#Intro">Introduction</a></li>
<ul>
<li><a href="#Exist">Existing Code in C++</a></li>
<li><a href="#ExistPy">Existing Code in Python</a></li>
</ul>
<li><a href="#Issues">Issues at Hand</a></li>
<ul>
<li><a href="#WhichOps">Which operators can chain?</a></li>
<li><a href="#WhichExprs">Which expressions can chain?</a></li>
<li><a href="#WhichSeqs">Which operator sequences can chain?</a></li>
<li><a href="#WhichConvs">Which about conversions or rvalues?</a></li>
<li><a href="#Folds">What about fold expressions?</a></li>
</ul>
<li><a href="#Proposal">Proposal</a></li>
<li><a href="#Acks">Acknowledgements</a></li>
</ul>
<a name="Revisions"> </a><h2>Revision History</h2>
<b>Since r0</b>. After discussion in Jacksonville:
<ul><li>Proposed changes to fold-expressions have been removed
<li>Once we determine that a comparison sequence could chain based on types, the sequence should either chain (based on operator sequence) or be ill-formed. The initial proposal allowed <code class="language-cpp">1 < 4 > 3</code> to continue to be well-formed (and yield <code class="language-cpp">false</code>), the new proposal makes it ill-formed.
<li>A new issue is now discussed regarding conversions and rvalues.
</ul>
<a name="Intro"> </a><h2>Introduction</h2>
<p>The idea of chaining comparisons was first put forth in <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0515r0.pdf">P0515R0</a>, in section 3.3, reproduced here in its entirety, with a clarifying change to the lambda.
<blockquote>C++17 has added fold expressions, which are very useful. However, as Voutilainen and others have reported, fold expressions do not currently work with comparisons. For example:
<pre><code class="language-cpp">if (args <...) // not possible with correct semantics in C++17</code></pre>
We can permit two-way comparisons to be chained with the usual pairwise mathematical meaning when the mathematical meaning preserves transitivity (which also always means they have equal precedence). The valid
chains are:
<ul>
<li>all <code class="language-cpp">==</code>, such as <code class="language-cpp">a == b == c == d;</code>
<li>all <code class="language-cpp">{<, <=}</code>, such as <code class="language-cpp">a < b <= c < d;</code> and
<li>all <code class="language-cpp">{>, >=}</code> (e.g., <code class="language-cpp">a >= b > c > d</code>).
</ul>
For example, this:
<pre><code class="language-cpp">if (a < b <= c < d)</code></pre>
would be rewritten by the compiler as-if as follows except with single evaluation of b and c:
<pre><code class="language-cpp">if ((a < b) && (b <= c) && (c < d)) // but no multiple eval of b and c</code></pre>
To illustrate how the compiler would implement this, here is one valid implementation that would satisfy the requirements including single evaluation, by just defining and invoking a lambda:
<pre><code class="language-cpp">auto __lambda = [&]{
// a and b both evaluated exactly once
auto&& __eval_b = b;
return a < __eval_b && [&]{
// c only evaluated if a < b. d only evaluated if the first two conditions are true
auto&& __eval_c = c;
return __eval_b <= __eval_c &&
__eval_c < d;
}();
};
if (__lambda())</code></pre>
<p>Chaining support was <a href="http://lists.isocpp.org/ext/2016/03/1047.php">one alternative suggested</a> by Ville Voutilainen to permit natural use of comparisons in C++17 fold expressions, such as <code class="language-cpp">if (args <...)</code>. However, chaining is also broadly useful throughout people’s code, so instead of baking the feature into fold expressions only, it’s better to provide general-purpose support that can also express concepts like <code class="language-cpp">first <= iter < last</code>. Providing general chaining also enables fold expressions as a special case (and with the “transitive” restriction above avoids the design pitfall of just providing chaining “for all comparison fold expressions,” when they should correctly be supported “for all comparison fold expressions except <code class="language-cpp">!=</code>” because <code class="language-cpp">!=</code> is not transitive).
<p>Without chaining, today we either perform double evaluation or introduce a temporary variable. I’ve many times wanted to write code like <code class="language-cpp">0 <= expr < max</code> without either evaluating expr twice or else having to invent a temporary variable (and usually a new scope) to store the evaluated value. A number of times, I’ve actually written the code without thinking, forgetting it wasn’t supported, and of course it either didn’t compile or did the wrong thing. As an example of “did the wrong thing,” this proposal does change the meaning of some code like the following that is legal today, but that is dubious because it probably doesn’t do what the programmer intended:
<pre><code class="language-cpp">int x = 1, y = 3, z = 2;
assert (x < y < z); // today, means “if (true < 2)” – succeeds</code></pre>
<p>In this proposal, the meaning of the condition would be <code class="language-cpp">if ((1 < 3) && (3 < 2))</code> and the assertion will fire. To use Stroustrup’s term, I consider this “code that deserves to be broken;” the change in meaning is probably fixing a bug. (Unless of course we do a code search and find examples that are actually intended.)
<p>Non-chained uses such as <code class="language-cpp">(a<b == c<d)</code> keep their existing meaning.</blockquote>
<a name="Exist"> </a><h3>Existing Code in C++</h3>
<p>The first question we sought to answer is the last question implied above: How much code exists today that uses chained comparison whose meaning would change in this proposal, and of those cases, how many were intentional (wanted the current semantics and so would be broken by this proposal) or unintentional (compile today, but are bugs and would be silently fixed by this proposal)? Many instances of the latter can be found in questions on StackOverflow <sup> <a href="https://stackoverflow.com/q/8889522/2069064">[1]</a> <a href="https://stackoverflow.com/q/5939077/2069064">[2]</a> <a href="https://stackoverflow.com/q/14433884/2069064">[3]</a> <a href="https://stackoverflow.com/q/46806239/2069064">[4]</a> <a href="https://stackoverflow.com/q/25965157/2069064">[5]</a> <a href="https://stackoverflow.com/q/38643022/2069064">[6]</a> <a href="https://stackoverflow.com/q/45385837/2069064">[7]</a> <a href="https://stackoverflow.com/q/20989496/2069064">[8]</a> <a href="https://stackoverflow.com/q/35564553/2069064">[9]</a> <a href="https://stackoverflow.com/q/42335710/2069064">[10]</a> <a href="https://stackoverflow.com/q/37470518/2069064">[11]</a> ...</sup>.
<p>To that end, we created a <a href="https://medium.com/@barryrevzin/chaining-comparisons-seeking-information-from-the-audience-abec909a1366">clang-tidy check</a> for all uses of chained comparison operators, ran it on many open source code bases, and solicited help from the C++ community to run it on their own. The check itself casts an intentionally wide net, matching any instance of <code class="language-cpp">a @ b @ c</code> for any of the six comparison operators, regardless of the types of these underlying expressions.
<p>Overall, what we found was:
<ul>
<li><b>Zero</b> instances of chained arithmetic comparisons that are correct today. That is, intentionally using the current standard behavior.
<li>Four instances of currently-erroneous arithmetic chaining, of the <code class="language-cpp">assert(0 <= ratio <= 1.0);</code> variety. These are bugs that compile today but don’t do what the programmer intended, but with this proposal would change in meaning to become correct.
<li>Many instances of using successive comparison operators in DSLs that overloaded these operators to give meaning unrelated to comparisons.
</ul>
<p>Finding zero instances in many large code bases where the current behavior is intended means this proposal has low negative danger (not a significant breaking change). However, a converse search shows this proposal has existing demand and high positive value: we searched for expressions that would benefit from chaining if it were available (such as <code class="language-cpp">idx >= 0 && idx < max</code>) and found <b>a few thousand</b> instances over just a few code bases. That means that this proposal would allow broad improvements across existing code bases, where linter/tidying tools would be able to suggest rewriting a large number of cases of existing code to be clearer, less brittle, and potentially more efficient (such as suggesting rewriting <code class="language-cpp">idx >= 0 && idx < max</code> to <code class="language-cpp">0 <= idx < max</code>, where the former is easy to write incorrectly now or under maintenance, and the latter is both clearer and potentially more efficient because it avoids multiple evaluation of <code class="language-cpp">idx</code>). It also adds strong justification to pursuing this proposal, because the data show the feature is already needed and its lack is frequently being worked around today by forcing programmers to write more brittle code that is easier to write incorrectly.
<a name="ExistPy"> </a><h3>Existing Code in Python</h3>
<p>While we have no experience with this feature in C++, Python has always supported <a href="https://docs.python.org/2/reference/expressions.html#comparisons">chaining comparisons</a>:
<blockquote><p>Unlike C, all comparison operations in Python have the same priority, which is lower than that of any arithmetic, shifting or bitwise operation. Also unlike C, expressions like <code class="language-cpp">a < b < c</code> have the interpretation that is conventional in mathematics [...]
<p>Comparisons can be chained arbitrarily, e.g., <code class="language-cpp">x < y <= z</code> is equivalent to <code class="language-cpp">x < y and y <= z</code>, except that <code class="language-cpp">y</code> is evaluated only once (but in both cases <code class="language-cpp">z</code> is not evaluated at all when <code class="language-cpp">x < y</code> is found to be false).
<p>Formally, if <code class="language-cpp">a</code>, <code class="language-cpp">b</code>, <code class="language-cpp">c</code>, …, <code class="language-cpp">y</code>, <code class="language-cpp">z</code> are expressions and <code class="language-cpp">op1</code>, <code class="language-cpp">op2</code>, …, <code class="language-cpp">opN</code> are comparison operators, then <code class="language-cpp">a op1 b op2 c ... y opN z</code> is equivalent to <code class="language-cpp">a op1 b and b op2 c and ... y opN z</code>, except that each expression is evaluated at most once.
<p>Note that <code class="language-cpp">a op1 b op2 c</code> doesn’t imply any kind of comparison between <code class="language-cpp">a</code> and <code class="language-cpp">c</code>, so that, e.g., <code class="language-cpp">x < y > z</code> is perfectly legal (though perhaps not pretty).</blockquote>
<p>The result is the ability to write natural comparison chains, without having to pairwise break them up with <code class="language-cpp">and</code>s.
<p>However, as the Python documentation itself points out, C++ has higher precedence for the operators <code class="language-cpp">{>, >=, <, <=}</code> than for the operators <code class="language-cpp">{==, !=}</code>. As a result, the expression <code class="language-cpp">a < b == c < d</code> today is parsed as the possibly-meaningful <code class="language-cpp">(a < b) == (c < d)</code>, and not the likely meaningless <code class="language-cpp">((a < b) == c) < d</code>. To interpret it as Python does would involve changing the underlying grammar of C++ and break such code (though we did not find any instances of this kind of mixed comparison, <i>i.e.</i> <code class="language-cpp">a < b == c</code>, in our search).
<a name="Issues"> </a><h2>Issues at Hand</h2>
There are several questions that need to be answered about how comparison chaining would work in C++.
<ul>
<li><b>Which operators?</b> Only consider chaining builtin comparison operators? Or also overloaded operators?
<li><b>Which expressions?</b> Only chain if each pairwise expression has type <code class="language-cpp">cv bool</code>? Or if each pairwise expression has a type that models the <code class="language-cpp">Boolean</code> concept from the <a href="https://timsong-cpp.github.io/cppwp/ranges-ts/concepts.lib.compare.boolean">Ranges TS</a> (which would, notably, include <code class="language-cpp">std::true_type</code>)? Any type at all?
<li><b>Which chains?</b> Only chain if either each operator is <code class="language-cpp">==</code>, if each is in <code class="language-cpp">{<,<=}</code>, or if each is in <code class="language-cpp">{>,>=}</code>? Or allow any combination of comparison operators?
<li><b>What about conversions and rvalues?</b> What do we do in the case where we have a comparison chain in which the constituent expressions are rvalues or the relevant comparison function requires a conversion?
<li><b>What about folds?</b> What should fold expressions do using a comparison operator?
</ul>
<p>Regardless of the choice of options, it should be noted that parentheses are significant here. Operator chaining would only apply to unparenthesized expressions. Adding parentheses would be one way of expressing intent. This is the same way that Python behaves today, where <code class="language-cpp">5 > 4 > 3</code> evaluates to <code class="language-cpp">True</code> (due to its evaluation as <code class="language-cpp">5 > 4 and 4 > 3</code>) while <code class="language-cpp">(5 > 4) > 3</code> evaluates as <code class="language-cpp">False</code> (due to its evaluation as <code class="language-cpp">True > 3</code>). If those situations arise where a programmer deliberately wants an unchained comparison, that is available to them with the use of parentheses.
<p>We will take each option separately.
<a name="WhichOps"></a><h3>Which operators can chain?</h3>
<p>We would prefer to see this apply to all operators, built-in and overloaded. This is different from <code class="language-cpp">&&</code> and <code class="language-cpp">||</code>, which change behavior when overloaded because then they don't short-circuit. However, there are many user-defined types for which comparison chaining would have desirable, well-defined behavior (e.g. <code class="language-cpp">std::pair</code>).
<a name="WhichExprs"></a><h3>Which expressions can chain?</h3>
<p>Why do we need a restriction at all? If we decide to only allow for chaining of builtin-operators, then this question is effectively moot. But once we get into the realm of overloaded operators, there are instances of chaining comparisons on objects where the behavior is decidedly <i>not</i> related to comparisons. Examples include <a href="https://github.com/boost-cmake/boost/blob/master/libs/multi_array/test/range1.cpp#L76">Boost.MultiArray</a>:
<pre><code class="language-cpp">range r6 = -3 <= range().stride(2) < 7; // not intended to be a chained comparison </code></pre>
or <a href="https://github.com/boost-cmake/boost/blob/master/libs/process/test/async_fut.cpp#L50-L57">Boost.Process</a>:
<pre><code class="language-cpp">bp::spawn(
master_test_suite().argv[1],
"test", "--prefix-once", "test",
bp::std_in < in_buf > fut_in, // not a chained comparison
bp::std_out > fut,
io_service,
ec
);</code></pre>
or <a href="https://github.com/boost-cmake/boost/blob/master/libs/spirit/test/qi/debug.cpp#L107-L108">Boost.Spirit</a>:
<pre><code class="language-cpp">rule<char const*> r;
r = '(' > int_ > ',' > int_ > ')'; // not a chained comparison</code></pre>
or even the less obvious <a href="https://github.com/catchorg/Catch2/blob/master/projects/SelfTest/UsageTests/BDD.tests.cpp#L54">Catch2</a>:
<pre><code class="language-cpp">std::vector<int> v;
REQUIRE(v.size() == 0); // macro expands to Catch::Decomposer() <= v.size() == 0, not a chained comparison</code></pre>
<p> Simply stating that <i>all</i> comparison chains get transformed into pairwise comparisons <code class="language-cpp">&&</code>-ed together would definitely break code. We cannot cast a net that wide.
<p> The simplest approach would be just to accept strictly boolean sub-expressions as candidates. That is, the expression <code class="language-cpp">a @ b @ c</code> is transformed into <code class="language-cpp">a @ b && b @ c</code> only if both <code class="language-cpp">a @ b</code> and <code class="language-cpp">b @ c</code> have type <code class="language-cpp">cv bool</code>. This would allow the most typical expected usage of range checking on arithmetic types or equality checking amongst many objects, while also avoiding changing the meanings of any of the above examples. If we allow overloaded operators as well, and those overloaded operators return <code class="language-cpp">bool</code> (as is typical, and as would be implicitly generated if using <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0515r3.pdf">the new <code class="language-cpp">operator<=></code></a>), then this would already allow for a wide variety of uses.
<p>However, there additionally exists some code that has comparison operators that, rather than returning <code class="language-cpp">bool</code> instead return <code class="language-cpp">std::true_type</code> or <code class="language-cpp">std::false_type</code>. Such return types are common in metaprogramming libraries, where we can encode the result into the type of the return object, instead of just the value. These types do satisfy the <code class="language-cpp">Boolean</code> concept without being strictly <code class="language-cpp">bool</code>, and seem safe to be included. Metaprogramming code could benefit from improved readability as well. It seems safe to include this wider range of possible types.
<p>For overloaded comparisons operators that do not return a <code class="language-cpp">Boolean</code> type, chaining can still be supported but just is not automatic: it is the responsibility of the overloaded operator author to make chaining work correctly for their comparison if that is what they want. We observe that these already exist, where overloaded operators like the Boost.MultiArray example already implement a flavor of chaining behavior even in the absence of precedents in the language.
<a name="WhichSeqs"></a><h3>Which operator sequences can chain?</h3>
<p>In its original presentation in P0515R0, only a specific subset of comparison operator sequences lead to chaining. Those operator sequences were precisely those that maintain transitivity:
<ul>
<li>all <code class="language-cpp">==</code>, such as <code class="language-cpp">a == b == c == d;</code>
<li>all <code class="language-cpp">{<, <=}</code>, such as <code class="language-cpp">a < b <= c < d;</code> and
<li>all <code class="language-cpp">{>, >=}</code>, such as <code class="language-cpp">a >= b > c > d</code>.
</ul>
<p>The ability to chain these operator sequences offers clear improvement to readability in real-world code, including major commercial projects:
<table style="width:100%">
<tr><th style="width:20%">(src)</th><th style="width:40%">Today</th><th style="width:4500%">Proposed</th></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/llvm-mirror/clang/blob/master/lib/AST/ExprConstant.cpp#L8406-L8407">clang</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">return Success((CR_r == APFloat::cmpEqual &&
CR_i == APFloat::cmpEqual), E);</code></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">return Success((CR_r == CR_i == APFloat::cmpEqual), E);</code></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Demangle/ItaniumDemangle.cpp#L1510">LLVM.Demangle</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">} else if ('1' <= first[1] && first[1] <= '9') {</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">} else if ('1' <= first[1] <= '9') {</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/boost-cmake/boost/blob/master/libs/numeric/interval/include/boost/numeric/interval/compare/explicit.hpp#L217">Boost.Numeric</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">return x.upper() >= y && y >= x.lower();</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">return x.upper() >= y >= x.lower();</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/boost-cmake/boost/blob/master/libs/regex/include/boost/regex/v4/match_results.hpp#L190">Boost.Regex</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if(sub < (int)m_subs.size() && (sub > 0))</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if(0 < sub < (int)m_subs.size())</code></pre></td></tr>
</table>
<p>The Python language, on the other hand, has no such restrictions. Any comparison operator sequence chains, but this appears to permit mainly pitfalls, not new good uses. In particular, it allows for some reasonable-appearing chains like <code class="language-cpp">a < b == c < d</code>, but also allows some less likely chains like <code class="language-cpp">a < b > c</code> and <code class="language-cpp">a != b != c</code>, which are known pitfalls - the Python documentation has to emphasize that these do not actually imply any relationship between <code class="language-cpp">a</code> and <code class="language-cpp">c</code>. We believe that further investigation in analyzing C++ code bases and languages like Python support the position that all of the chains initially recommended in P0515R0 are useful and should be supported, and that all of the chains not recommended in P0515R0 are unuseful or actively harmful, and so should not be interpreted as chained (any code that writes such chains almost certainly will get something unintended).
<p>We were able to find several expressions of the unrestricted variety that might theoretically be shorted by chaining, but (a) the following rewrites could never actually be made to work without changing the precedence of <code class="language-cpp">==</code> and <code class="language-cpp">!=</code> with respect to <code class="language-cpp"><</code>, <code class="language-cpp"><=</code>, <code class="language-cpp">></code>, and <code class="language-cpp">>=</code> which would be an impossibly large breaking change to consider, and (b) even if we did that, the resulting code is not actually better. In our opinion, it is visually ambiguous and unclear in all cases. Discussion in Jacksonville indicated that keeping the current unchained behavior for non-transitive comparison sequences would be needlessly confusing as it give too many different potential meanings to an expression. We therefore suggest that the non-transitive comparison sequences be ill-formed:
<table style="width:100%">
<tr><th style="width:20%">(src)</th><th style="width:40%">Today</th><th style="width:40%">Python-like chaining<br />(proposed <font color="red">ill-formed</font>)</th></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/boost-cmake/boost/blob/master/libs/math/include/boost/math/special_functions/gamma.hpp#L157">Boost.Math</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if((floor(z) == z) && (z < max_factorial<T>::value))</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if((floor(z) == z < max_factorial<T>::value))</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/DeadStoreElimination.cpp#L372">LLVM.Transforms</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if (ObjectSize == Later.Size &&
ObjectSize >= Earlier.Size)</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if (Later.Size == ObjectSize >= Earlier.Size)</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Support/APFloat.cpp#L609">LLVM.Support</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">assert(count != 0 &&
count <= APFloatBase::integerPartWidth / 4);</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">assert(0 != count <=
APFloatBase::integerPartWidth / 4);</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/CodeGen/TargetSchedule.cpp#L60">LLVM.CodeGen</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">assert((LCM >= A && LCM >= B)
&& "LCM overflow");</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">assert((A <= LCM >= B) && "LCM overflow");</code></pre></td></tr>
<tr><td style="vertical-align:middle;text-align:center"><a href="https://github.com/boost-cmake/boost/blob/master/libs/intrusive/include/boost/intrusive/circular_list_algorithms.hpp#L283">Boost.Intrusive</a></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if(n != p && i != p)</code></pre></td>
<td><pre style="background:transparent;border:0px"><code class="language-cpp">if(n != p != i)</code></pre></td></tr>
</table>
<a name="WhichConvs"></a><h3>What about conversions or rvalues?</h3>
<p>An important question issue is how to deal with expressions in which a call to a comparison function would require a user-defined conversions to take place.
Consider a piece of code such as:
<pre><code class="language-cpp">struct X { ... };
bool operator<=(X const&, X const& );
struct Y { operator X() const; };
bool in_between(X const& a, Y const& y, X const& b) {
// today
return a <= y && y <= b;
// with chaining
return a <= y <= b;
}</code></pre>
<p>Today, we have to write <code class="language-cpp">y</code> twice, so the fact the conversion to <code class="language-cpp">X</code> is performed twice is unsurprising. But the same two conversions would have to happen in the chained comparison as well, which may be more surprising - as <code class="language-cpp">y</code> is only referenced once.
<p>An additional question is what do we do if one of the comparison functions actually would move from its arguments?
<pre><code class="language-cpp">struct A { ... }; // imagine this has a move constructor that modifies its source
bool operator<(A, A);
A mid();
bool in_between(A const& left, A const& right) {
return left < mid() < right;
}</code></pre>
<p>If <code class="language-cpp">A</code> both (a) has a non-trivial move constructor and (b) has comparisons that take by value, then this could move from <code class="language-cpp">mid()</code>'s returned object twice. But frankly, we believe that this is just plain weird, for two reasons. First, comparisons are logically const operations and should never change the values of their arguments; a comparison that could move from its argument in a way that modifies the source's value is nonsensical. Second, a type that is designed to be passed by value to comparisons or other functions (such as <code class="language-cpp">int</code> or <code class="language-cpp">std::string_view</code>) is naturally a cheap-to-copy value type that does not have a move constructor that modifies the source object (or indeed, does something different from copying). We cannot come up with a defensible example where this would be a problem, but we would invite anyone to show a plausible example of such code.
<p>This leads to the question of what to do with with middle arguments that are rvalues. We have three options:
<ol>
<li>After evaluating the middle argument, we forward it to both sides of the comparison: <pre><code class="language-cpp">auto&& __mid = mid();
return left < __FWD(mid) && __FWD(mid) < right;</pre></code>
This leads us to moving from that <code class="language-cpp">A</code> twice, which is a non-starter.
<li>We only forward at most one time:<pre><code class="language-cpp">auto&& __mid = mid();
return left < mid && __FWD(mid) < right;</pre></code>This means we're treating the <i>same</i> expression in <i>two different</i> ways, even though it's only named once. This seems unnecessarily difficult to reason about, and we're not sure it would provide commensurate benefit.
<li>We just treat all the expressions as lvalues, always materializing a temporary and using it: <pre><code class="language-cpp">auto&& __mid = mid();
return left < __mid && __mid < right;</code></pre>
</ol>
<p>We believe the third option is the only viable option. Any kind of attempt at restricting rvalue expressions in the middle of chain would restrict useful comparisons. The implication is that expressions that look like rvalues would be treated as lvalues, so that expressions that look like they should lead to moves may actually lead to copies, and expressions that are named once could still lead to two conversions. We're not concerned about the first problem since, as described above, we expect that comparison functions either take their arguments by value and are cheap to copy (so that there simply is no difference between incurring a move and incurring a copy) or take their arguments by reference to const (so that neither a move nor a copy happens to begin with).
<p>And we could do something better about the second problem. We could allow, or even mandate (or allow now and mandate in the future), the optimization that if both uses of the duplicated expression invoke the same conversion (whether converting constructor or conversion function) to match the selected operators' respective parameters, we materialize and reuse the converted result. This has precedent in copy elision and guaranteed copy elision.
<p>That is, the following example: <pre><code class="language-cpp">struct X { ... };
bool operator<=(X const&, X const& );
struct Y { operator X() const; };
Y foo();
bool in_between(X const& a, X const& b) {
return a <= foo() <= b;
}</code></pre> would behave as if:<pre><code class="language-cpp">bool in_between(X const& a, X const& b) {
auto&& __materialized_foo = foo();
auto&& __converted_foo = __materialized_foo.operator X();
return a <= __converted_foo && __converted_foo <= b;
}</code></pre>
This lets us have multiple benefits: we can chain the comparison instead of splitting it up, the middle expressions are only evaluated (at most) one time, and the necessary conversions are only evaluated (at most) one time as well.
<a name="Folds"></a><h3>What about fold expressions?</h3>
<p>Today, all six of the comparison operators are valid binary operators to use in a <a href="http://eel.is/c++draft/expr.prim.fold#1">fold expression</a>, but the expansion rules always produce <a href="http://eel.is/c++draft/temp.variadic#9">parenthesized sub-expressions</a>. That is:
<pre><code class="language-cpp">template <typename... Ts>
bool ordered(Ts... vals) {
return (... <= vals);
}
ordered(4, 3, 2, 1); // instantiated as ((4 <= 3) <= 2) <= 1, evaluates to true, even with this proposal</code></pre>
<p>As mentioned earlier, parentheses are significant, so having fold expressions expand as parenthesized would continue to inhibit comparison chaining. This makes today's fold expressions for comparisons not useful and actually buggy.
<p>The initial version of this proposal suggested that fold expressions over comparison operators instantiate as unparenthesized, to allow them to be useful and correct. However, parenthesized sub-expressions are a key part of how fold expressions actually work. It would be a large change, both conceptually and in terms of implementation, to remove them - a change that fails to offer comparable large benefit. We therefore propose no change to fold expressions at this time.
<a name="Proposal"></a><h2>Proposal</h2>
<p>A maximal, unparenthesized expression of the form <code class="language-cpp">a @1 b @2 c @3 ... @# n</code>, where each <code class="language-cpp">@</code> is one of the six two-way comparison operators, that contains at least two comparison operators will now be evaluated according to the following rules:
<ul>
<li>If each pairwise comparison (that is <code class="language-cpp">a @1 b</code>, <code class="language-cpp">b @2 c</code>, etc.) would evaluate to a type that models the <code class="language-cpp">Boolean</code> concept, then:
<ul><li>If it is not the case that every operator is either <code class="language-cpp">==</code>, or one of <code class="language-cpp">{<, <=}</code>, or one of <code class="language-cpp">{>, >=}</code> (that is, the sequence of operators would not be transitive), then the expression is ill-formed.
<li>Otherwise, the expression shall be evaluated as if <code class="language-cpp">(a @1 b) && (b @2 c) && ... && (m @# n)</code>, except that each sub-expression shall be evaluated at most once time (including temporary materialization) and each of the "middle" terms will always be passed to the corresponding comparison functions as lvalues. If any of these "middle" terms need to undergo the same conversion to match its two selected operators' respective parameters, an implementation may elide the second conversion and reuse the same converted value as the argument for both parameters.
<p>In other words, approximately equivalently to: <pre><code class="language-cpp">[&]{
auto&& __eval_b = b;
return (a @1 __eval_b) && [&]{
auto&& __eval_c = c;
return (__eval_b @2 __eval_c) && [&]{
// ...
}();
}();
}()</code></pre>
</ul>
<li>Otherwise, the behavior remains as it does today.
</ul>
<p>Any DSLs currently existing would continue to work properly, since the results of each sub-expression would not model <code class="language-cpp">Boolean</code>. The non-transitive chains (such as <code class="language-cpp">a != b != c</code>) would be made ill-formed by the first sub-bullet. If non-transitive comparisons are required, parentheses may be used to break up sub-expressions to avoid this rule (e.g. <code class="language-cpp">(a < b) == (c < d)</code> would behave as it does today).
<p>The second sub-bullet, the as-lvalue rule, provides a path to allow chained comparisons with <code class="language-cpp">string_view</code> and <code class="language-cpp">string</code>, other rvalues or conversions, as well as providing an easy rule to remember. From the conversion section, <code class="language-cpp">a <= y <= b</code> would be a valid comparison chain that would evaluate as <code class="language-cpp">auto&& __y = y; (a <= __y) && (__y <= b)</code>, which would lead to one invocation of <code class="language-cpp">Y::operator X() const</code> (the second would be allowed to be elided).
<a name="Acks"> </a><h2>Acknowledgements</h2>
<p>Thanks to T.C. for help in properly specifying the search for chained comparisons and innumerable feedback about various issues. Thanks to Nicolas Lesser and Titus Winters for contributing data for live use of comparisons.
</body>
</html>