--0000000000001598610577afba23
Content-Type: text/plain; charset="UTF-8"

On Sun, Oct 7, 2018 at 11:35 PM Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
wrote:

> On Saturday, October 6, 2018 at 9:55:04 AM UTC-7, Phil Miller wrote:
>>
>> Present Proposal
>>
>> Add a free function defined as follows to namespace std, in an
>> appropriate header TBD:
>>
>> template <typename T, typename U>
>>
>> bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu)
>>
>> {
>>
>>  intptr_t bt = pt, et = pt+nt;
>>
>>  intptr_t bu = pu, eu = pu+nu;
>>
>>  return (et <= bu) || (eu <= bt);
>>
>> }
>>
>> Requirements:
>>
>>    -
>>
>>    The pointers pt and pu are valid.
>>    -
>>
>>    The expressions pt+nt and pu+nu are valid. (i.e. they point to
>>    elements within the same array as pt and pu, respectively, or to one past
>>    the end, including the case where pt is a pointer is to a non-array object
>>    and nt is 1 (or pu and nu, respectively))
>>
>>
> I don't know if this nit is really relevant to the rest of the proposal,
> but that definition of `disjoint` has problems with boundary conditions,
> e.g. if (et < bt) or (eu < bu).  (I mean, if the addition bt+nt would have
> overflowed.)  It would be interesting and useful to come up with a
> bulletproof definition of `disjoint` that actually worked in practice, just
> to get the implementation out there in the wild, even if it never gets
> standardized.
>

Hi Arthur,

Thanks for the feedback. The latter requirement about the validity of
expressions pt+nt was meant to cover the case noted, but I think it
actually covers the overflow case you bring up as well. That overflow is
UB, I believe, and is also very likely forming a pointer outside the bounds
of the object pointed to by pt. So, I think the nit *is* relevant to the
proposal, in that it's another case to note as forbidden by the requirement
that the end-pointer expressions be valid. Does that seem right to you?

At any rate, I've actually written roughly the necessary logic for the
'bullet-proof' version previously, in a different setting, so it's not too
hard to reproduce an attempt at it here:

template <typename T, typename U>

bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu)

{

 intptr_t bt = pt;

 intptr_t bu = pu;


if (bt == bu)

return false;


if (bt < bu) {

return (bu - bt) < (sizeof(T) * nt);

} else {

return (bt - bu) < (sizeof(U) * nu);

}

}

The general idiom for avoiding the overflow in the addition is to compare
the relevant distances instead. As formulated here, this of course still
has potential overflows in the multiplication expressions. Then we get into
the finicky business of rounding the difference up and dividing by
sizeof(T), while making sure that the tested condition still means what we
want it to.

Phil

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAMDbWJFVVUxL%3D3XaDnJNqTvNK7Mc8PPAMusu9_JdcSvOc%2BXc%2BA%40mail.gmail.com.

--0000000000001598610577afba23
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Sun=
, Oct 7, 2018 at 11:35 PM Arthur O&#39;Dwyer &lt;<a href=3D"mailto:arthur.j=
..odwyer@gmail.com">arthur.j.odwyer@gmail.com</a>&gt; wrote:<br></div><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex"><div dir=3D"ltr">On Saturday, October 6, 2018 at 9=
:55:04 AM UTC-7, Phil Miller wrote:<blockquote class=3D"gmail_quote" style=
=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"ltr"><span style=3D"font-size:14pt;font-family:Arial;color:rgb=
(67,67,67);background-color:transparent;font-weight:400;font-style:normal;f=
ont-variant:normal;text-decoration:none;vertical-align:baseline;white-space=
:pre-wrap">Present Proposal</span><p dir=3D"ltr" style=3D"line-height:1.38;=
margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family=
:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-s=
tyle:normal;font-variant:normal;text-decoration:none;vertical-align:baselin=
e;white-space:pre-wrap">Add a free function defined as follows to namespace=
 std, in an appropriate header TBD:</span></p><br><p dir=3D"ltr" style=3D"l=
ine-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:=
11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:=
transparent;font-weight:400;font-style:normal;font-variant:normal;text-deco=
ration:none;vertical-align:baseline;white-space:pre-wrap">template &lt;type=
name T, typename U&gt;</span></p><p dir=3D"ltr" style=3D"line-height:1.38;m=
argin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:=
&quot;Courier New&quot;;color:rgb(0,0,0);background-color:transparent;font-=
weight:400;font-style:normal;font-variant:normal;text-decoration:none;verti=
cal-align:baseline;white-space:pre-wrap">bool disjoint(const T* pt, size_t =
nt, const U* pu, size_t nu)</span></p><p dir=3D"ltr" style=3D"line-height:1=
..38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-fa=
mily:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:transparent;=
font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;=
vertical-align:baseline;white-space:pre-wrap">{</span></p><p dir=3D"ltr" st=
yle=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"fo=
nt-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);backgroun=
d-color:transparent;font-weight:400;font-style:normal;font-variant:normal;t=
ext-decoration:none;vertical-align:baseline;white-space:pre-wrap"> =C2=A0in=
tptr_t bt =3D pt, et =3D pt+nt;</span></p><p dir=3D"ltr" style=3D"line-heig=
ht:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;fon=
t-family:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:transpar=
ent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:n=
one;vertical-align:baseline;white-space:pre-wrap"> =C2=A0intptr_t bu =3D pu=
, eu =3D pu+nu;</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;marg=
in-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:&qu=
ot;Courier New&quot;;color:rgb(0,0,0);background-color:transparent;font-wei=
ght:400;font-style:normal;font-variant:normal;text-decoration:none;vertical=
-align:baseline;white-space:pre-wrap"> =C2=A0return (et &lt;=3D bu) || (eu =
&lt;=3D bt);</span></p><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:=
0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:&quot;Cour=
ier New&quot;;color:rgb(0,0,0);background-color:transparent;font-weight:400=
;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:=
baseline;white-space:pre-wrap">}</span></p><br><p dir=3D"ltr" style=3D"line=
-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11p=
t;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weig=
ht:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-=
align:baseline;white-space:pre-wrap">Requirements:</span></p><ul style=3D"m=
argin-top:0pt;margin-bottom:0pt"><li dir=3D"ltr" style=3D"list-style-type:d=
isc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:tran=
sparent;font-weight:400;font-style:normal;font-variant:normal;text-decorati=
on:none;vertical-align:baseline;white-space:pre-wrap"><p dir=3D"ltr" style=
=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-=
size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;f=
ont-weight:400;font-style:normal;font-variant:normal;text-decoration:none;v=
ertical-align:baseline;white-space:pre-wrap">The pointers pt and pu are val=
id.</span></p></li><li dir=3D"ltr" style=3D"list-style-type:disc;font-size:=
11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-w=
eight:400;font-style:normal;font-variant:normal;text-decoration:none;vertic=
al-align:baseline;white-space:pre-wrap"><p dir=3D"ltr" style=3D"line-height=
:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-=
family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;=
font-style:normal;font-variant:normal;text-decoration:none;vertical-align:b=
aseline;white-space:pre-wrap">The expressions pt+nt and pu+nu are valid. (i=
..e. they point to elements within the same array as pt and pu, respectively=
, or to one past the end, including the case where pt is a pointer is to a =
non-array object and nt is 1 (or pu and nu, respectively))</span></p></li><=
/ul></div></blockquote><div><br></div><div>I don&#39;t know if this nit is =
really relevant to the rest of the proposal, but that definition of `disjoi=
nt` has problems with boundary conditions, e.g. if (et &lt; bt) or (eu &lt;=
 bu). =C2=A0(I mean, if the addition bt+nt would have overflowed.) =C2=A0It=
 would be interesting and useful to come up with a bulletproof definition o=
f `disjoint` that actually worked in practice, just to get the implementati=
on out there in the wild, even if it never gets standardized.</div></div></=
blockquote><div>=C2=A0</div><div>Hi Arthur,</div><div><br></div><div>Thanks=
 for the feedback. The latter requirement about the validity of expressions=
 pt+nt was meant to cover the case noted, but I think it actually covers th=
e overflow case you bring up as well. That overflow is UB, I believe, and i=
s also very likely forming a pointer outside the bounds of the object point=
ed to by pt. So, I think the nit <i>is</i> relevant to the proposal, in tha=
t it&#39;s another case to note as forbidden by the requirement that the en=
d-pointer expressions be valid. Does that seem right to you?</div><div><br>=
</div><div>At any rate, I&#39;ve actually written roughly the necessary log=
ic for the &#39;bullet-proof&#39; version previously, in a different settin=
g, so it&#39;s not too hard to reproduce an attempt at it here:</div><div><=
br></div><div><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margi=
n-bottom:0pt"><span style=3D"font-size:11pt;font-family:&quot;Courier New&q=
uot;;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-sty=
le:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;=
white-space:pre-wrap">template &lt;typename T, typename U&gt;</span></p><p =
dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><sp=
an style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,=
0,0);background-color:transparent;font-weight:400;font-style:normal;font-va=
riant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-w=
rap">bool disjoint(const T* pt, size_t nt, const U* pu, size_t nu)</span></=
p><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt=
"><span style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:r=
gb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;fo=
nt-variant:normal;text-decoration:none;vertical-align:baseline;white-space:=
pre-wrap">{</span></p><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0=
pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:&quot;Couri=
er New&quot;;color:rgb(0,0,0);background-color:transparent;font-weight:400;=
font-style:normal;font-variant:normal;text-decoration:none;vertical-align:b=
aseline;white-space:pre-wrap"> =C2=A0intptr_t bt =3D pt;</span></p><p dir=
=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span =
style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0=
);background-color:transparent;font-weight:400;font-style:normal;font-varia=
nt:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap=
"> =C2=A0intptr_t bu =3D pu;</span></p><p dir=3D"ltr" style=3D"line-height:=
1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-f=
amily:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:transparent=
;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none=
;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p style=3D"l=
ine-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:=
11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:=
transparent;font-weight:400;font-style:normal;font-variant:normal;text-deco=
ration:none;vertical-align:baseline;white-space:pre-wrap">  if (bt =3D=3D b=
u)</span></p><p style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"=
><span style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:rg=
b(0,0,0);background-color:transparent;font-weight:400;font-style:normal;fon=
t-variant:normal;text-decoration:none;vertical-align:baseline;white-space:p=
re-wrap">    return false;<br></span></p><p dir=3D"ltr" style=3D"line-heigh=
t:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font=
-family:&quot;Courier New&quot;;color:rgb(0,0,0);background-color:transpare=
nt;font-weight:400;font-style:normal;font-variant:normal;text-decoration:no=
ne;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p style=3D=
"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-siz=
e:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);background-colo=
r:transparent;font-weight:400;font-style:normal;font-variant:normal;text-de=
coration:none;vertical-align:baseline;white-space:pre-wrap">  if (bt &lt; b=
u) {</span></p><p style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0p=
t"><span style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:=
rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;f=
ont-variant:normal;text-decoration:none;vertical-align:baseline;white-space=
:pre-wrap">    return (bu - bt) &lt; (sizeof(T) * nt);<br></span></p><p sty=
le=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"fon=
t-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);background=
-color:transparent;font-weight:400;font-style:normal;font-variant:normal;te=
xt-decoration:none;vertical-align:baseline;white-space:pre-wrap">  } else {=
</span></p><p style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><=
span style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(=
0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-=
variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre=
-wrap"><span style=3D"font-size:11pt;font-family:&quot;Courier New&quot;;co=
lor:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:norm=
al;font-variant:normal;text-decoration:none;vertical-align:baseline;white-s=
pace:pre-wrap">    return (bt - bu) &lt; (sizeof(U) * nu);</span></span></p=
><p style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=
=3D"font-size:11pt;font-family:&quot;Courier New&quot;;color:rgb(0,0,0);bac=
kground-color:transparent;font-weight:400;font-style:normal;font-variant:no=
rmal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  }=
<br></span></p><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;marg=
in-bottom:0pt"><span style=3D"font-size:11pt;font-family:&quot;Courier New&=
quot;;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-st=
yle:normal;font-variant:normal;text-decoration:none;vertical-align:baseline=
;white-space:pre-wrap">}</span></p></div><div><br></div><div>The general id=
iom for avoiding the overflow in the addition is to compare the relevant di=
stances instead. As formulated here, this of course still has potential ove=
rflows in the multiplication expressions. Then we get into the finicky busi=
ness of rounding the difference up and dividing by sizeof(T), while making =
sure that the tested condition still means what we want it to.<br></div><di=
v><br></div><div>Phil<br></div></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAMDbWJFVVUxL%3D3XaDnJNqTvNK7Mc8PPAMu=
su9_JdcSvOc%2BXc%2BA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAMDbWJFVVU=
xL%3D3XaDnJNqTvNK7Mc8PPAMusu9_JdcSvOc%2BXc%2BA%40mail.gmail.com</a>.<br />

--0000000000001598610577afba23--

.