--0000000000005c4094056fa189ef
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Some functions may keep looping for an unbounded amount of iterations, such
as std::distance. This may cause DoS.
I propose to add *_n versions so things are controlled in case of invalid
input.

Ideas?


--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?

--=20
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 e=
mail 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/CAFdMc-1LTe1WQhJAtapEojWOOP%3DyntLNnPvDAL5gJ%2B0=
1HmjN%3DA%40mail.gmail.com.

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

<div dir=3D"ltr">Some functions may keep looping for an unbounded amount of=
 iterations, such as std::distance. This may cause DoS.<div>I propose to ad=
d *_n versions so things are controlled in case of invalid input.<br clear=
=3D"all"><div><br></div><div>Ideas?</div><div><br></div><div><br></div>-- <=
br><div class=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=
=80=99s got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>=
Who=E2=80=99d never, ever start an argument?<br>Who never shows a bit of te=
mperament?<br>Who&#39;s never wrong but always right?<br>Who&#39;d never dr=
eam of starting a fight?<br>Who get stuck with all the bad luck? </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/CAFdMc-1LTe1WQhJAtapEojWOOP%3DyntLNnP=
vDAL5gJ%2B01HmjN%3DA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1LTe=
1WQhJAtapEojWOOP%3DyntLNnPvDAL5gJ%2B01HmjN%3DA%40mail.gmail.com</a>.<br />

--0000000000005c4094056fa189ef--

.

------=_Part_29234_219041126.1530115187387
Content-Type: multipart/alternative;
 boundary="----=_Part_29235_189295740.1530115187387"

------=_Part_29235_189295740.1530115187387
Content-Type: text/plain; charset="UTF-8"

On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
>
> Some functions may keep looping for an unbounded amount of iterations,
> such as std::distance. This may cause DoS.
> I propose to add *_n versions so things are controlled in case of invalid
> input.
>

1. What does a function return if it reached `n`? Is that considered to
produce a correct iterator, or are you just catching invalid input? If it's
the latter, then I imagine some form of exception would be thrown. Is that
what we want?

2. What is an appropriate "n" for detecting invalid input for a particular
range, and how do you communicate that value to those who directly call
`std::distance_n` or similar functions? After all, `std::distance` and the
like are usually used deep down in various systems; even if they were using
`distance_n`, how would you tell them what the right "n" is?

--
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/4932fdae-3a5a-4212-bf89-b75f855e9634%40isocpp.org.

------=_Part_29235_189295740.1530115187387
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel G=
utson wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">S=
ome functions may keep looping for an unbounded amount of iterations, such =
as std::distance. This may cause DoS.<div>I propose to add *_n versions so =
things are controlled in case of invalid input.<br clear=3D"all"></div></di=
v></blockquote><div><br></div><div>1. What does a function return if it rea=
ched `n`? Is that considered to produce a correct iterator, or are you just=
 catching invalid input? If it&#39;s the latter, then I imagine some form o=
f exception would be thrown. Is that what we want?<br></div><div><br></div>=
<div>2. What is an appropriate &quot;n&quot; for detecting invalid input fo=
r a particular range, and how do you communicate that value to those who di=
rectly call `std::distance_n` or similar functions? After all, `std::distan=
ce` and the like are usually used deep down in various systems; even if the=
y were using `distance_n`, how would you tell them what the right &quot;n&q=
uot; is?<br></div><br></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/4932fdae-3a5a-4212-bf89-b75f855e9634%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/4932fdae-3a5a-4212-bf89-b75f855e9634=
%40isocpp.org</a>.<br />

------=_Part_29235_189295740.1530115187387--

------=_Part_29234_219041126.1530115187387--

.

--000000000000560f22056fa1ca53
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <jmckesson@gmail.com> wrote:

> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
>>
>> Some functions may keep looping for an unbounded amount of iterations,
>> such as std::distance. This may cause DoS.
>> I propose to add *_n versions so things are controlled in case of invali=
d
>> input.
>>
>
> 1. What does a function return if it reached `n`? Is that considered to
> produce a correct iterator, or are you just catching invalid input? If it=
's
> the latter, then I imagine some form of exception would be thrown. Is tha=
t
> what we want?
>

I want to survey the idea at high level first, then we can dig into the
implementation, expected behavior, interface.


>
> 2. What is an appropriate "n" for detecting invalid input for a particula=
r
> range, and how do you communicate that value to those who directly call
> `std::distance_n` or similar functions? After all, `std::distance` and th=
e
> like are usually used deep down in various systems; even if they were usi=
ng
> `distance_n`, how would you tell them what the right "n" is?
>

There are two non-mutually-exclusive approaches about this.
1- iteration limit
1.1 - based on known boundaries (e.g. memory space knowlege)
1.2 - based on measurements
1.2.1 - experimentally determined
1.2.2 - run-time determined based on running statistics
2- time limit

Maybe a better interface (discussion I'd like to postpone a little bit
after getting more consensus) could be to accept a caller-provided
termination_policy, and offer 3 basic policies (count-based, time-based,
and an OR-combining policy).


>
>
> --
> 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/4932fdae-3a5a-4212-
> bf89-b75f855e9634%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/4932fdae-3a=
5a-4212-bf89-b75f855e9634%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoot=
er>
> .
>



--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?

--=20
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 e=
mail 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/CAFdMc-2rvWkDyoEVt5hf8PXpba5TRTsy_3vPxRDkk2Z8oKR=
GKQ%40mail.gmail.com.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <span dir=3D"ltr">&lt;<a =
href=3D"mailto:jmckesson@gmail.com" target=3D"_blank">jmckesson@gmail.com</=
a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><sp=
an class=3D"">On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Guts=
on 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">Some func=
tions may keep looping for an unbounded amount of iterations, such as std::=
distance. This may cause DoS.<div>I propose to add *_n versions so things a=
re controlled in case of invalid input.<br clear=3D"all"></div></div></bloc=
kquote><div><br></div></span><div>1. What does a function return if it reac=
hed `n`? Is that considered to produce a correct iterator, or are you just =
catching invalid input? If it&#39;s the latter, then I imagine some form of=
 exception would be thrown. Is that what we want?<br></div></div></blockquo=
te><div><br></div><div>I want to survey the idea at high level first, then =
we can dig into the implementation, expected behavior, interface.</div><div=
>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div></div><di=
v><br></div><div>2. What is an appropriate &quot;n&quot; for detecting inva=
lid input for a particular range, and how do you communicate that value to =
those who directly call `std::distance_n` or similar functions? After all, =
`std::distance` and the like are usually used deep down in various systems;=
 even if they were using `distance_n`, how would you tell them what the rig=
ht &quot;n&quot; is?</div></div></blockquote><div><br></div><div>There are =
two non-mutually-exclusive approaches about this.</div><div>1- iteration li=
mit</div><div>1.1 - based on known boundaries (e.g. memory space knowlege)<=
/div><div>1.2 - based on measurements</div><div>1.2.1 - experimentally dete=
rmined</div><div>1.2.2 - run-time determined based on running statistics</d=
iv><div>2- time limit</div><div><br></div><div>Maybe a better interface (di=
scussion I&#39;d like to postpone a little bit after getting more consensus=
) could be to accept a caller-provided termination_policy, and offer 3 basi=
c policies (count-based, time-based, and an OR-combining policy).</div><div=
>=C2=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><span=
 class=3D"HOEnZb"><font color=3D"#888888"><br></font></span></div><span cla=
ss=3D"HOEnZb"><font color=3D"#888888"><br></font></span></div><span class=
=3D"HOEnZb"><font color=3D"#888888">

<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" target=3D"_=
blank">std-proposals+unsubscribe@<wbr>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">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/4932fdae-3a5a-4212-bf89-b75f855e9634%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/<wbr>isocpp.org/d/msgid/std-<wbr>proposals/4932=
fdae-3a5a-4212-<wbr>bf89-b75f855e9634%40isocpp.org</a><wbr>.<br>
</font></span></blockquote></div><br><br clear=3D"all"><div><br></div>-- <b=
r><div class=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=
=80=99s got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>=
Who=E2=80=99d never, ever start an argument?<br>Who never shows a bit of te=
mperament?<br>Who&#39;s never wrong but always right?<br>Who&#39;d never dr=
eam of starting a fight?<br>Who get stuck with all the bad luck? </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/CAFdMc-2rvWkDyoEVt5hf8PXpba5TRTsy_3vP=
xRDkk2Z8oKRGKQ%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-2rvWkDyoEV=
t5hf8PXpba5TRTsy_3vPxRDkk2Z8oKRGKQ%40mail.gmail.com</a>.<br />

--000000000000560f22056fa1ca53--

.

------=_Part_43516_1207349919.1530116314538
Content-Type: multipart/alternative;
 boundary="----=_Part_43517_307327165.1530116314538"

------=_Part_43517_307327165.1530116314538
Content-Type: text/plain; charset="UTF-8"

On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gutson wrote:
>
> On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <jmck...@gmail.com
> <javascript:>> wrote:
>
>> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
>>>
>>> Some functions may keep looping for an unbounded amount of iterations,
>>> such as std::distance. This may cause DoS.
>>> I propose to add *_n versions so things are controlled in case of
>>> invalid input.
>>>
>>
>> 1. What does a function return if it reached `n`? Is that considered to
>> produce a correct iterator, or are you just catching invalid input? If it's
>> the latter, then I imagine some form of exception would be thrown. Is that
>> what we want?
>>
>
> I want to survey the idea at high level first, then we can dig into the
> implementation, expected behavior, interface.
>

Without considering expected behavior, the idea cannot reasonably be
considered at the high level. If the caller cannot tell the difference
between early termination and the getting a legitimate distance
`distance_n`, then that will strongly affect who will and will not use this
function. If it's not considered valid behavior, then it changes how users
have to interact with it, which again affects who will and will not be
willing to call it.

So yes, these are things that must be considered, even from a high level.
They affect the usability of the tool. And since this tool exists purely
for safety reasons, then such usability needs to be taken into account.
There's no point in having "safe" interfaces nobody is willing to use,
after all.

2. What is an appropriate "n" for detecting invalid input for a particular
>> range, and how do you communicate that value to those who directly call
>> `std::distance_n` or similar functions? After all, `std::distance` and the
>> like are usually used deep down in various systems; even if they were using
>> `distance_n`, how would you tell them what the right "n" is?
>>
>
> There are two non-mutually-exclusive approaches about this.
> 1- iteration limit
> 1.1 - based on known boundaries (e.g. memory space knowlege)
> 1.2 - based on measurements
> 1.2.1 - experimentally determined
> 1.2.2 - run-time determined based on running statistics
> 2- time limit
>
> Maybe a better interface (discussion I'd like to postpone a little bit
> after getting more consensus) could be to accept a caller-provided
> termination_policy, and offer 3 basic policies (count-based, time-based,
> and an OR-combining policy).
>

It doesn't matter what the information is. I want to know how you get that
information from the high-level code that supplied the potentially invalid
iterators (and therefore is the code that has some idea of what such
boundary conditions ought to be) to the low-level code that will actually
call `std::distance` (which probably has no idea what a reasonable boundary
is).

Take `std::lower_bound`. It probably uses `std::advance` or `std::next`,
which would have similar boundary condition functions. `lower_bound` has *no
idea* what a reasonable boundary condition would be; only the caller would
know. So do we now need a version of `lower_bound` that takes this boundary
condition as an optional parameter?

--
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/c3a0e827-0580-4c49-af1e-fd1b192f7734%40isocpp.org.

------=_Part_43517_307327165.1530116314538
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel G=
utson wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><=
div><div class=3D"gmail_quote">On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bola=
s <span dir=3D"ltr">&lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfus=
cated-mailto=3D"QWEM27ziCAAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&=
#39;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&=
#39;;return true;">jmck...@gmail.com</a>&gt;</span> wrote:<br><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;=
padding-left:1ex"><div dir=3D"ltr"><span>On Wednesday, June 27, 2018 at 11:=
47:50 AM UTC-4, Daniel Gutson 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">Some functions may keep looping for an unbounded amount o=
f iterations, such as std::distance. This may cause DoS.<div>I propose to a=
dd *_n versions so things are controlled in case of invalid input.<br clear=
=3D"all"></div></div></blockquote><div><br></div></span><div>1. What does a=
 function return if it reached `n`? Is that considered to produce a correct=
 iterator, or are you just catching invalid input? If it&#39;s the latter, =
then I imagine some form of exception would be thrown. Is that what we want=
?<br></div></div></blockquote><div><br></div><div>I want to survey the idea=
 at high level first, then we can dig into the implementation, expected beh=
avior, interface.</div></div></div></div></blockquote><div><br></div><div>W=
ithout considering expected behavior, the idea cannot reasonably be conside=
red at the high level. If the caller cannot tell the difference between ear=
ly termination and the getting a legitimate distance `distance_n`, then tha=
t will strongly affect who will and will not use this function. If it&#39;s=
 not considered valid behavior, then it changes how users have to interact =
with it, which again affects who will and will not be willing to call it.</=
div><div><br></div><div>So yes, these are things that must be considered, e=
ven from a high level. They affect the usability of the tool. And since thi=
s tool exists purely for safety reasons, then such usability needs to be ta=
ken into account. There&#39;s no point in having &quot;safe&quot; interface=
s nobody is willing to use, after all.</div><div><br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #c=
cc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_quot=
e"><div></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div></div><d=
iv></div><div>2. What is an appropriate &quot;n&quot; for detecting invalid=
 input for a particular range, and how do you communicate that value to tho=
se who directly call `std::distance_n` or similar functions? After all, `st=
d::distance` and the like are usually used deep down in various systems; ev=
en if they were using `distance_n`, how would you tell them what the right =
&quot;n&quot; is?</div></div></blockquote><div><br></div><div>There are two=
 non-mutually-exclusive approaches about this.</div><div>1- iteration limit=
</div><div>1.1 - based on known boundaries (e.g. memory space knowlege)</di=
v><div>1.2 - based on measurements</div><div>1.2.1 - experimentally determi=
ned</div><div>1.2.2 - run-time determined based on running statistics</div>=
<div>2- time limit</div><div><br></div><div>Maybe a better interface (discu=
ssion I&#39;d like to postpone a little bit after getting more consensus) c=
ould be to accept a caller-provided termination_policy, and offer 3 basic p=
olicies (count-based, time-based, and an OR-combining policy).</div></div><=
/div></div></blockquote><div><br></div><div>It doesn&#39;t matter what the =
information is. I want to know how you get that information from the high-l=
evel code that supplied the potentially invalid iterators (and therefore is=
 the code that has some idea of what such boundary conditions ought to be) =
to the low-level code that will actually call `std::distance` (which probab=
ly has no idea what a reasonable boundary is).<br></div><div><br></div><div=
>Take `std::lower_bound`. It probably uses `std::advance` or `std::next`, w=
hich would have similar boundary condition functions. `lower_bound` has <i>=
no idea</i> what a reasonable boundary condition would be; only the caller =
would know. So do we now need a version of `lower_bound` that takes this bo=
undary condition as an optional parameter?<br></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/c3a0e827-0580-4c49-af1e-fd1b192f7734%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-fd1b192f7734=
%40isocpp.org</a>.<br />

------=_Part_43517_307327165.1530116314538--

------=_Part_43516_1207349919.1530116314538--

.

--000000000000e7b3cd056fa21bcc
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <jmckesson@gmail.com> wrote:

> On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gutson wrote:
>>
>> On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <jmck...@gmail.com> wrote:
>>
>>> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
>>>>
>>>> Some functions may keep looping for an unbounded amount of iterations,
>>>> such as std::distance. This may cause DoS.
>>>> I propose to add *_n versions so things are controlled in case of
>>>> invalid input.
>>>>
>>>
>>> 1. What does a function return if it reached `n`? Is that considered to
>>> produce a correct iterator, or are you just catching invalid input? If =
it's
>>> the latter, then I imagine some form of exception would be thrown. Is t=
hat
>>> what we want?
>>>
>>
>> I want to survey the idea at high level first, then we can dig into the
>> implementation, expected behavior, interface.
>>
>
> Without considering expected behavior, the idea cannot reasonably be
> considered at the high level. If the caller cannot tell the difference
> between early termination and the getting a legitimate distance
> `distance_n`, then that will strongly affect who will and will not use th=
is
> function. If it's not considered valid behavior, then it changes how user=
s
> have to interact with it, which again affects who will and will not be
> willing to call it.
>
> So yes, these are things that must be considered, even from a high level.
> They affect the usability of the tool. And since this tool exists purely
> for safety reasons, then such usability needs to be taken into account.
> There's no point in having "safe" interfaces nobody is willing to use,
> after all.
>
> 2. What is an appropriate "n" for detecting invalid input for a particula=
r
>>> range, and how do you communicate that value to those who directly call
>>> `std::distance_n` or similar functions? After all, `std::distance` and =
the
>>> like are usually used deep down in various systems; even if they were u=
sing
>>> `distance_n`, how would you tell them what the right "n" is?
>>>
>>
>> There are two non-mutually-exclusive approaches about this.
>> 1- iteration limit
>> 1.1 - based on known boundaries (e.g. memory space knowlege)
>> 1.2 - based on measurements
>> 1.2.1 - experimentally determined
>> 1.2.2 - run-time determined based on running statistics
>> 2- time limit
>>
>> Maybe a better interface (discussion I'd like to postpone a little bit
>> after getting more consensus) could be to accept a caller-provided
>> termination_policy, and offer 3 basic policies (count-based, time-based,
>> and an OR-combining policy).
>>
>
> It doesn't matter what the information is. I want to know how you get tha=
t
> information from the high-level code that supplied the potentially invali=
d
> iterators (and therefore is the code that has some idea of what such
> boundary conditions ought to be) to the low-level code that will actually
> call `std::distance` (which probably has no idea what a reasonable bounda=
ry
> is).
>
> Take `std::lower_bound`. It probably uses `std::advance` or `std::next`,
> which would have similar boundary condition functions. `lower_bound` has =
*no
> idea* what a reasonable boundary condition would be; only the caller
> would know. So do we now need a version of `lower_bound` that takes this
> boundary condition as an optional parameter?
>


namespace std {

template< class InputIt*, class TerminationPolicy* >
constexpr *std::optional<*typename
std::iterator_traits<InputIt>::difference_type*>*
    distance( InputIt first, InputIt last, *TerminationPolicy&&
terminationPolicy* );

}

I'm using 'optional' but could be 'expected' or 'outcome' depending on
their progress (I'm not up to date about them).

How does that look?



> --
> 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/c3a0e827-0580-4c49-
> af1e-fd1b192f7734%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c3a0e827-05=
80-4c49-af1e-fd1b192f7734%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoot=
er>
> .
>



--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?

--=20
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 e=
mail 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/CAFdMc-0O79k-JzmGbWCNe_beNWYtcGOkjQ2FNroSComXVr6=
Xzw%40mail.gmail.com.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <span dir=3D"ltr">&lt;<a h=
ref=3D"mailto:jmckesson@gmail.com" target=3D"_blank">jmckesson@gmail.com</a=
>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><d=
iv dir=3D"ltr">On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gut=
son wrote:<span class=3D"gmail-"><blockquote class=3D"gmail_quote" style=3D=
"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-le=
ft:1ex"><div dir=3D"ltr"><div><div class=3D"gmail_quote">On Wed, Jun 27, 20=
18 at 12:59 PM, Nicol Bolas <span dir=3D"ltr">&lt;<a rel=3D"nofollow">jmck.=
...@gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddi=
ng-left:1ex"><div dir=3D"ltr"><span>On Wednesday, June 27, 2018 at 11:47:50=
 AM UTC-4, Daniel Gutson wrote:<blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left=
:1ex"><div dir=3D"ltr">Some functions may keep looping for an unbounded amo=
unt of iterations, such as std::distance. This may cause DoS.<div>I propose=
 to add *_n versions so things are controlled in case of invalid input.<br =
clear=3D"all"></div></div></blockquote><div><br></div></span><div>1. What d=
oes a function return if it reached `n`? Is that considered to produce a co=
rrect iterator, or are you just catching invalid input? If it&#39;s the lat=
ter, then I imagine some form of exception would be thrown. Is that what we=
 want?<br></div></div></blockquote><div><br></div><div>I want to survey the=
 idea at high level first, then we can dig into the implementation, expecte=
d behavior, interface.</div></div></div></div></blockquote><div><br></div><=
/span><div>Without considering expected behavior, the idea cannot reasonabl=
y be considered at the high level. If the caller cannot tell the difference=
 between early termination and the getting a legitimate distance `distance_=
n`, then that will strongly affect who will and will not use this function.=
 If it&#39;s not considered valid behavior, then it changes how users have =
to interact with it, which again affects who will and will not be willing t=
o call it.</div><div><br></div><div>So yes, these are things that must be c=
onsidered, even from a high level. They affect the usability of the tool. A=
nd since this tool exists purely for safety reasons, then such usability ne=
eds to be taken into account. There&#39;s no point in having &quot;safe&quo=
t; interfaces nobody is willing to use, after all.</div><span class=3D"gmai=
l-"><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div d=
ir=3D"ltr"><div><div class=3D"gmail_quote"><div></div><blockquote class=3D"=
gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(20=
4,204,204);padding-left:1ex"><div dir=3D"ltr"><div></div><div></div><div>2.=
 What is an appropriate &quot;n&quot; for detecting invalid input for a par=
ticular range, and how do you communicate that value to those who directly =
call `std::distance_n` or similar functions? After all, `std::distance` and=
 the like are usually used deep down in various systems; even if they were =
using `distance_n`, how would you tell them what the right &quot;n&quot; is=
?</div></div></blockquote><div><br></div><div>There are two non-mutually-ex=
clusive approaches about this.</div><div>1- iteration limit</div><div>1.1 -=
 based on known boundaries (e.g. memory space knowlege)</div><div>1.2 - bas=
ed on measurements</div><div>1.2.1 - experimentally determined</div><div>1.=
2.2 - run-time determined based on running statistics</div><div>2- time lim=
it</div><div><br></div><div>Maybe a better interface (discussion I&#39;d li=
ke to postpone a little bit after getting more consensus) could be to accep=
t a caller-provided termination_policy, and offer 3 basic policies (count-b=
ased, time-based, and an OR-combining policy).</div></div></div></div></blo=
ckquote><div><br></div></span><div>It doesn&#39;t matter what the informati=
on is. I want to know how you get that information from the high-level code=
 that supplied the potentially invalid iterators (and therefore is the code=
 that has some idea of what such boundary conditions ought to be) to the lo=
w-level code that will actually call `std::distance` (which probably has no=
 idea what a reasonable boundary is).<br></div><div><br></div><div>Take `st=
d::lower_bound`. It probably uses `std::advance` or `std::next`, which woul=
d have similar boundary condition functions. `lower_bound` has <i>no idea</=
i> what a reasonable boundary condition would be; only the caller would kno=
w. So do we now need a version of `lower_bound` that takes this boundary co=
ndition as an optional parameter?<br></div></div></blockquote><div><br></di=
v><div><br></div><div>namespace std {</div><div><br></div><div><div>templat=
e&lt; class InputIt<b>, class TerminationPolicy</b> &gt;</div><div>constexp=
r <b>std::optional&lt;</b>typename std::iterator_traits&lt;InputIt&gt;::dif=
ference_type<b>&gt;</b>=C2=A0</div><div>=C2=A0 =C2=A0 distance( InputIt fir=
st, InputIt last, <b>TerminationPolicy&amp;&amp; terminationPolicy</b> );</=
div></div><div>=C2=A0</div><div>}</div><div><br></div><div>I&#39;m using &#=
39;optional&#39; but could be &#39;expected&#39; or &#39;outcome&#39; depen=
ding on their progress (I&#39;m not up to date about them).</div><div><br><=
/div><div>How does that look?</div><div><br></div><div>=C2=A0</div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px=
 solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div></div></div=
><span class=3D"gmail-">

<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" target=3D"_=
blank">std-proposals+unsubscribe@<wbr>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br></span>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-fd1b192f7734%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/<wbr>isocpp.org/d/msgid/std-<wbr>proposals/c3a0=
e827-0580-4c49-<wbr>af1e-fd1b192f7734%40isocpp.org</a><wbr>.<br>
</blockquote></div><br><br clear=3D"all"><div><br></div>-- <br><div class=
=3D"gmail_signature">Who=E2=80=99s got the sweetest disposition?<br>One gue=
ss, that=E2=80=99s who?<br>Who=E2=80=99d never, ever start an argument?<br>=
Who never shows a bit of temperament?<br>Who&#39;s never wrong but always r=
ight?<br>Who&#39;d never dream of starting a fight?<br>Who get stuck with a=
ll the bad luck? </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/CAFdMc-0O79k-JzmGbWCNe_beNWYtcGOkjQ2F=
NroSComXVr6Xzw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-0O79k-JzmG=
bWCNe_beNWYtcGOkjQ2FNroSComXVr6Xzw%40mail.gmail.com</a>.<br />

--000000000000e7b3cd056fa21bcc--

.

--00000000000012a676056fa22590
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson <danielgutson@gmail.com>
wrote:

>
>
> On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <jmckesson@gmail.com> wrote:
>
>> On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gutson wrote:
>>>
>>> On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <jmck...@gmail.com> wrote=
:
>>>
>>>> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
>>>>>
>>>>> Some functions may keep looping for an unbounded amount of iterations=
,
>>>>> such as std::distance. This may cause DoS.
>>>>> I propose to add *_n versions so things are controlled in case of
>>>>> invalid input.
>>>>>
>>>>
>>>> 1. What does a function return if it reached `n`? Is that considered t=
o
>>>> produce a correct iterator, or are you just catching invalid input? If=
 it's
>>>> the latter, then I imagine some form of exception would be thrown. Is =
that
>>>> what we want?
>>>>
>>>
>>> I want to survey the idea at high level first, then we can dig into the
>>> implementation, expected behavior, interface.
>>>
>>
>> Without considering expected behavior, the idea cannot reasonably be
>> considered at the high level. If the caller cannot tell the difference
>> between early termination and the getting a legitimate distance
>> `distance_n`, then that will strongly affect who will and will not use t=
his
>> function. If it's not considered valid behavior, then it changes how use=
rs
>> have to interact with it, which again affects who will and will not be
>> willing to call it.
>>
>> So yes, these are things that must be considered, even from a high level=
..
>> They affect the usability of the tool. And since this tool exists purely
>> for safety reasons, then such usability needs to be taken into account.
>> There's no point in having "safe" interfaces nobody is willing to use,
>> after all.
>>
>> 2. What is an appropriate "n" for detecting invalid input for a
>>>> particular range, and how do you communicate that value to those who
>>>> directly call `std::distance_n` or similar functions? After all,
>>>> `std::distance` and the like are usually used deep down in various sys=
tems;
>>>> even if they were using `distance_n`, how would you tell them what the
>>>> right "n" is?
>>>>
>>>
>>> There are two non-mutually-exclusive approaches about this.
>>> 1- iteration limit
>>> 1.1 - based on known boundaries (e.g. memory space knowlege)
>>> 1.2 - based on measurements
>>> 1.2.1 - experimentally determined
>>> 1.2.2 - run-time determined based on running statistics
>>> 2- time limit
>>>
>>> Maybe a better interface (discussion I'd like to postpone a little bit
>>> after getting more consensus) could be to accept a caller-provided
>>> termination_policy, and offer 3 basic policies (count-based, time-based=
,
>>> and an OR-combining policy).
>>>
>>
>> It doesn't matter what the information is. I want to know how you get
>> that information from the high-level code that supplied the potentially
>> invalid iterators (and therefore is the code that has some idea of what
>> such boundary conditions ought to be) to the low-level code that will
>> actually call `std::distance` (which probably has no idea what a reasona=
ble
>> boundary is).
>>
>> Take `std::lower_bound`. It probably uses `std::advance` or `std::next`,
>> which would have similar boundary condition functions. `lower_bound` has=
 *no
>> idea* what a reasonable boundary condition would be; only the caller
>> would know. So do we now need a version of `lower_bound` that takes this
>> boundary condition as an optional parameter?
>>
>
>
> namespace std {
>
> template< class InputIt*, class TerminationPolicy* >
> constexpr *std::optional<*typename std::iterator_traits<InputIt>:
> :difference_type*>*
>     distance( InputIt first, InputIt last, *TerminationPolicy&&
> terminationPolicy* );
>
> }
>
> I'm using 'optional' but could be 'expected' or 'outcome' depending on
> their progress (I'm not up to date about them).
>
> How does that look?
>

I forgot to propose the interface of the policy: alternative -
1) bool TerminationPolicy::operator(), where 'true' means terminate.
2) bool TerminationPolicy::terminate(), true means terminate
3) bool TerminationPolicy::keep_running(), true means not to terminate.


>
>
>
>> --
>> You received this message because you are subscribed to the Google Group=
s
>> "ISO C++ Standard - Future Proposals" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> 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/is
>> ocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-
>> fd1b192f7734%40isocpp.org
>> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0=
580-4c49-af1e-fd1b192f7734%40isocpp.org?utm_medium=3Demail&utm_source=3Dfoo=
ter>
>> .
>>
>
>
>
> --
> Who=E2=80=99s got the sweetest disposition?
> One guess, that=E2=80=99s who?
> Who=E2=80=99d never, ever start an argument?
> Who never shows a bit of temperament?
> Who's never wrong but always right?
> Who'd never dream of starting a fight?
> Who get stuck with all the bad luck?
>



--=20
Who=E2=80=99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?

--=20
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 e=
mail 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/CAFdMc-1R3foMw2X5wdCp1b_g55cuEyW%2BGzPZr_e_YW3LF=
FA1PA%40mail.gmail.com.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:danielgutson@gmail.com" target=3D"_blank">danielgutson@gmai=
l.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"l=
tr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quote"><span cla=
ss=3D"">On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <span dir=3D"ltr">&lt;=
<a href=3D"mailto:jmckesson@gmail.com" target=3D"_blank">jmckesson@gmail.co=
m</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex=
"><div dir=3D"ltr">On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel=
 Gutson wrote:<span class=3D"m_-8006337345269791103gmail-"><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid r=
gb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div><div class=3D"gmail=
_quote">On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <span dir=3D"ltr">&lt=
;<a rel=3D"nofollow">jmck...@gmail.com</a>&gt;</span> wrote:<br><blockquote=
 class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so=
lid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><span>On Wednesday,=
 June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:<blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex"><div dir=3D"ltr">Some functions may keep l=
ooping for an unbounded amount of iterations, such as std::distance. This m=
ay cause DoS.<div>I propose to add *_n versions so things are controlled in=
 case of invalid input.<br clear=3D"all"></div></div></blockquote><div><br>=
</div></span><div>1. What does a function return if it reached `n`? Is that=
 considered to produce a correct iterator, or are you just catching invalid=
 input? If it&#39;s the latter, then I imagine some form of exception would=
 be thrown. Is that what we want?<br></div></div></blockquote><div><br></di=
v><div>I want to survey the idea at high level first, then we can dig into =
the implementation, expected behavior, interface.</div></div></div></div></=
blockquote><div><br></div></span><div>Without considering expected behavior=
, the idea cannot reasonably be considered at the high level. If the caller=
 cannot tell the difference between early termination and the getting a leg=
itimate distance `distance_n`, then that will strongly affect who will and =
will not use this function. If it&#39;s not considered valid behavior, then=
 it changes how users have to interact with it, which again affects who wil=
l and will not be willing to call it.</div><div><br></div><div>So yes, thes=
e are things that must be considered, even from a high level. They affect t=
he usability of the tool. And since this tool exists purely for safety reas=
ons, then such usability needs to be taken into account. There&#39;s no poi=
nt in having &quot;safe&quot; interfaces nobody is willing to use, after al=
l.</div><span class=3D"m_-8006337345269791103gmail-"><div><br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1p=
x solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><div></div><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e=
x"><div dir=3D"ltr"><div></div><div></div><div>2. What is an appropriate &q=
uot;n&quot; for detecting invalid input for a particular range, and how do =
you communicate that value to those who directly call `std::distance_n` or =
similar functions? After all, `std::distance` and the like are usually used=
 deep down in various systems; even if they were using `distance_n`, how wo=
uld you tell them what the right &quot;n&quot; is?</div></div></blockquote>=
<div><br></div><div>There are two non-mutually-exclusive approaches about t=
his.</div><div>1- iteration limit</div><div>1.1 - based on known boundaries=
 (e.g. memory space knowlege)</div><div>1.2 - based on measurements</div><d=
iv>1.2.1 - experimentally determined</div><div>1.2.2 - run-time determined =
based on running statistics</div><div>2- time limit</div><div><br></div><di=
v>Maybe a better interface (discussion I&#39;d like to postpone a little bi=
t after getting more consensus) could be to accept a caller-provided termin=
ation_policy, and offer 3 basic policies (count-based, time-based, and an O=
R-combining policy).</div></div></div></div></blockquote><div><br></div></s=
pan><div>It doesn&#39;t matter what the information is. I want to know how =
you get that information from the high-level code that supplied the potenti=
ally invalid iterators (and therefore is the code that has some idea of wha=
t such boundary conditions ought to be) to the low-level code that will act=
ually call `std::distance` (which probably has no idea what a reasonable bo=
undary is).<br></div><div><br></div><div>Take `std::lower_bound`. It probab=
ly uses `std::advance` or `std::next`, which would have similar boundary co=
ndition functions. `lower_bound` has <i>no idea</i> what a reasonable bound=
ary condition would be; only the caller would know. So do we now need a ver=
sion of `lower_bound` that takes this boundary condition as an optional par=
ameter?<br></div></div></blockquote><div><br></div><div><br></div></span><d=
iv>namespace std {</div><div><br></div><div><div>template&lt; class InputIt=
<b>, class TerminationPolicy</b> &gt;</div><div>constexpr <b>std::optional&=
lt;</b>typename std::iterator_traits&lt;InputIt&gt;:<wbr>:difference_type<b=
>&gt;</b>=C2=A0</div><div>=C2=A0 =C2=A0 distance( InputIt first, InputIt la=
st, <b>TerminationPolicy&amp;&amp; terminationPolicy</b> );</div></div><div=
>=C2=A0</div><div>}</div><div><br></div><div>I&#39;m using &#39;optional&#3=
9; but could be &#39;expected&#39; or &#39;outcome&#39; depending on their =
progress (I&#39;m not up to date about them).</div><div><br></div><div>How =
does that look?</div></div></div></div></blockquote><div><br></div><div>I f=
orgot to propose the interface of the policy: alternative -</div><div>1) bo=
ol <span style=3D"font-size:small;background-color:rgb(255,255,255);text-de=
coration-style:initial;text-decoration-color:initial;float:none;display:inl=
ine">TerminationPolicy::</span>operator(), where &#39;true&#39; means termi=
nate.</div><div>2) bool TerminationPolicy::terminate(), true means terminat=
e</div><div>3) bool=C2=A0<span style=3D"font-size:small;background-color:rg=
b(255,255,255);text-decoration-style:initial;text-decoration-color:initial;=
float:none;display:inline">TerminationPolicy::keep_running(), true means no=
t to terminate.</span></div><div>=C2=A0</div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><sp=
an class=3D""><div><br></div><div>=C2=A0</div><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20=
4);padding-left:1ex"><div dir=3D"ltr"><div></div></div><span class=3D"m_-80=
06337345269791103gmail-">

<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" target=3D"_=
blank">std-proposals+unsubscribe@isoc<wbr>pp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br></span>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-fd1b192f7734%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/is<wbr>ocpp.org/d/msgid/std-proposals<wbr>/c3a0=
e827-0580-4c49-af1e-<wbr>fd1b192f7734%40isocpp.org</a>.<br>
</blockquote></span></div><br><br clear=3D"all"><span class=3D""><div><br><=
/div>-- <br><div class=3D"m_-8006337345269791103gmail_signature">Who=E2=80=
=99s got the sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=
=E2=80=99d never, ever start an argument?<br>Who never shows a bit of tempe=
rament?<br>Who&#39;s never wrong but always right?<br>Who&#39;d never dream=
 of starting a fight?<br>Who get stuck with all the bad luck? </div>
</span></div></div>
</blockquote></div><br><br clear=3D"all"><div><br></div>-- <br><div class=
=3D"gmail_signature" data-smartmail=3D"gmail_signature">Who=E2=80=99s got t=
he sweetest disposition?<br>One guess, that=E2=80=99s who?<br>Who=E2=80=99d=
 never, ever start an argument?<br>Who never shows a bit of temperament?<br=
>Who&#39;s never wrong but always right?<br>Who&#39;d never dream of starti=
ng a fight?<br>Who get stuck with all the bad luck? </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/CAFdMc-1R3foMw2X5wdCp1b_g55cuEyW%2BGz=
PZr_e_YW3LFFA1PA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1R3foMw2=
X5wdCp1b_g55cuEyW%2BGzPZr_e_YW3LFFA1PA%40mail.gmail.com</a>.<br />

--00000000000012a676056fa22590--

.

--0000000000003823f7056fa238fe
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

In general I think that allowing limits to iterations does make some sense.
Not necessarily in the case of contract-breaking calls (which I could
imagine sweeping insufficiently checked code under the rug), but in the
case of expensive loops in which you only want to check if the output
exceeds certain bounds.

For example, in checking if std::distance between two ordered elements on a
1000000-element linked list is greater than, say, 50, replacing
std::distance with std::distance_n(..., ..., 50) could be faster due to
reduced iterations and loop unrolling if N is known at compile time.

I do have a question, the answer to which will determine how many people
get confused by the output. How should this impact loops with
type-dependant complexity? Say I run std::distance_n(a, b, N) with:
A) a, b satisfying RandomAccessIterator (constant complexity, no benefit
from bounding the result)
B) a, b NOT satisfying RandomAccessIterator (linear, possible benefit from
bounding the result)

In case (B) I'd expect the result to be between 0 and N. In the case (A),
should I also expect this, even when the bound would be completely
artificial? And how would negative results be treated?


On Wed, 27 Jun 2018, 16:47 Daniel Gutson, <danielgutson@gmail.com> wrote:

> Some functions may keep looping for an unbounded amount of iterations,
> such as std::distance. This may cause DoS.
> I propose to add *_n versions so things are controlled in case of invalid
> input.
>
> Ideas?
>
>
> --
> Who=E2=80=99s got the sweetest disposition?
> One guess, that=E2=80=99s who?
> Who=E2=80=99d never, ever start an argument?
> Who never shows a bit of temperament?
> Who's never wrong but always right?
> Who'd never dream of starting a fight?
> Who get stuck with all the bad luck?
>
> --
> 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/CAFdMc-1LTe1=
WQhJAtapEojWOOP%3DyntLNnPvDAL5gJ%2B01HmjN%3DA%40mail.gmail.com
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1LTe=
1WQhJAtapEojWOOP%3DyntLNnPvDAL5gJ%2B01HmjN%3DA%40mail.gmail.com?utm_medium=
=3Demail&utm_source=3Dfooter>
> .
>

--=20
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 e=
mail 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/CAC%2B0CCMKmCg%3DL802SvARbm1F7BdOvOSPutB0c6aA8xS=
_gehetw%40mail.gmail.com.

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

<div dir=3D"auto">In general I think that allowing limits to iterations doe=
s make some sense. Not necessarily in the case of contract-breaking calls (=
which I could imagine sweeping insufficiently checked code under the rug), =
but in the case of expensive loops in which you only want to check if the o=
utput exceeds certain bounds.<div dir=3D"auto"><br></div><div dir=3D"auto">=
For example, in checking if std::distance between two ordered elements on a=
 1000000-element linked list is greater than, say, 50, replacing std::dista=
nce with std::distance_n(..., ..., 50) could be faster due to reduced itera=
tions and loop unrolling if N is known at compile time.<div dir=3D"auto"><b=
r></div><div dir=3D"auto">I do have a question, the answer to which will de=
termine how many people get confused by the output. How should this impact =
loops with type-dependant complexity? Say I run std::distance_n(a, b, N) wi=
th:</div><div dir=3D"auto">A) a, b satisfying RandomAccessIterator (constan=
t complexity, no benefit from bounding the result)</div><div dir=3D"auto">B=
) a, b NOT satisfying RandomAccessIterator (linear, possible benefit from b=
ounding the result)</div><div dir=3D"auto"><br></div><div dir=3D"auto">In c=
ase (B) I&#39;d expect the result to be between 0 and N. In the case (A), s=
hould I also expect this, even when the bound would be completely artificia=
l? And how would negative results be treated?</div><div dir=3D"auto"><br></=
div></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Wed, 27 =
Jun 2018, 16:47 Daniel Gutson, &lt;<a href=3D"mailto:danielgutson@gmail.com=
" rel=3D"noreferrer noreferrer" target=3D"_blank">danielgutson@gmail.com</a=
>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0=
 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Some =
functions may keep looping for an unbounded amount of iterations, such as s=
td::distance. This may cause DoS.<div>I propose to add *_n versions so thin=
gs are controlled in case of invalid input.<br clear=3D"all"><div><br></div=
><div>Ideas?</div><div><br></div><div><br></div>-- <br><div class=3D"m_6803=
762566553020418m_5748895786842865683m_-2431815379619471394gmail_signature" =
data-smartmail=3D"gmail_signature">Who=E2=80=99s got the sweetest dispositi=
on?<br>One guess, that=E2=80=99s who?<br>Who=E2=80=99d never, ever start an=
 argument?<br>Who never shows a bit of temperament?<br>Who&#39;s never wron=
g but always right?<br>Who&#39;d never dream of starting a fight?<br>Who ge=
t stuck with all the bad luck? </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" rel=3D"nore=
ferrer noreferrer noreferrer" target=3D"_blank">std-proposals+unsubscribe@i=
socpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">std-propos=
als@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/CAFdMc-1LTe1WQhJAtapEojWOOP%3DyntLNnP=
vDAL5gJ%2B01HmjN%3DA%40mail.gmail.com?utm_medium=3Demail&amp;utm_source=3Df=
ooter" rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">https://g=
roups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1LTe1WQhJAtapEoj=
WOOP%3DyntLNnPvDAL5gJ%2B01HmjN%3DA%40mail.gmail.com</a>.<br>
</blockquote></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/CAC%2B0CCMKmCg%3DL802SvARbm1F7BdOvOSP=
utB0c6aA8xS_gehetw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter"=
>https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAC%2B0CCMKmC=
g%3DL802SvARbm1F7BdOvOSPutB0c6aA8xS_gehetw%40mail.gmail.com</a>.<br />

--0000000000003823f7056fa238fe--

.

------=_Part_7505_782932071.1530222692191
Content-Type: multipart/alternative;
 boundary="----=_Part_7506_1560310572.1530222692192"

------=_Part_7506_1560310572.1530222692192
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wednesday, June 27, 2018 at 9:31:22 AM UTC-7, Daniel Gutson wrote:
>
> On Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson <daniel...@gmail.com>=20
> wrote:
>
>> On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <jmck...@gmail.com> wrote:
>>
>>> On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gutson wrote:
>>>>
>>>> On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas <jmck...@gmail.com>=20
>>>> wrote:
>>>>
>>>>> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote=
:
>>>>>>
>>>>>> Some functions may keep looping for an unbounded amount of=20
>>>>>> iterations, such as std::distance. This may cause DoS.
>>>>>> I propose to add *_n versions so things are controlled in case of=20
>>>>>> invalid input.
>>>>>>
>>>>>
>>>>> 1. What does a function return if it reached `n`? Is that considered=
=20
>>>>> to produce a correct iterator, or are you just catching invalid input=
? If=20
>>>>> it's the latter, then I imagine some form of exception would be throw=
n. Is=20
>>>>> that what we want?
>>>>>
>>>>
>>>> I want to survey the idea at high level first, then we can dig into th=
e=20
>>>> implementation, expected behavior, interface.
>>>>
>>>
>>> Without considering expected behavior, the idea cannot reasonably be=20
>>> considered at the high level. If the caller cannot tell the difference=
=20
>>> between early termination and the getting a legitimate distance=20
>>> `distance_n`, then that will strongly affect who will and will not use =
this=20
>>> function. If it's not considered valid behavior, then it changes how us=
ers=20
>>> have to interact with it, which again affects who will and will not be=
=20
>>> willing to call it.
>>>
>>> So yes, these are things that must be considered, even from a high=20
>>> level. They affect the usability of the tool. And since this tool exist=
s=20
>>> purely for safety reasons, then such usability needs to be taken into=
=20
>>> account. There's no point in having "safe" interfaces nobody is willing=
 to=20
>>> use, after all.
>>>
>>> 2. What is an appropriate "n" for detecting invalid input for a=20
>>>>> particular range, and how do you communicate that value to those who=
=20
>>>>> directly call `std::distance_n` or similar functions? After all,=20
>>>>> `std::distance` and the like are usually used deep down in various sy=
stems;=20
>>>>> even if they were using `distance_n`, how would you tell them what th=
e=20
>>>>> right "n" is?
>>>>>
>>>>
>>>> There are two non-mutually-exclusive approaches about this.
>>>> 1- iteration limit
>>>> 1.1 - based on known boundaries (e.g. memory space knowlege)
>>>> 1.2 - based on measurements
>>>> 1.2.1 - experimentally determined
>>>> 1.2.2 - run-time determined based on running statistics
>>>> 2- time limit
>>>>
>>>> Maybe a better interface (discussion I'd like to postpone a little bit=
=20
>>>> after getting more consensus) could be to accept a caller-provided=20
>>>> termination_policy, and offer 3 basic policies (count-based, time-base=
d,=20
>>>> and an OR-combining policy).
>>>>
>>>
>>> It doesn't matter what the information is. I want to know how you get=
=20
>>> that information from the high-level code that supplied the potentially=
=20
>>> invalid iterators (and therefore is the code that has some idea of what=
=20
>>> such boundary conditions ought to be) to the low-level code that will=
=20
>>> actually call `std::distance` (which probably has no idea what a reason=
able=20
>>> boundary is).
>>>
>>> Take `std::lower_bound`. It probably uses `std::advance` or `std::next`=
,=20
>>> which would have similar boundary condition functions. `lower_bound` ha=
s *no=20
>>> idea* what a reasonable boundary condition would be; only the caller=20
>>> would know. So do we now need a version of `lower_bound` that takes thi=
s=20
>>> boundary condition as an optional parameter?
>>>
>>
>>
>> namespace std {
>>
>> template< class InputIt*, class TerminationPolicy* >
>> constexpr *std::optional<*typename=20
>> std::iterator_traits<InputIt>::difference_type*>*=20
>>     distance( InputIt first, InputIt last, *TerminationPolicy&&=20
>> terminationPolicy* );
>> =20
>> }
>>
>> I'm using 'optional' but could be 'expected' or 'outcome' depending on=
=20
>> their progress (I'm not up to date about them).
>>
>> How does that look?
>>
>
> I forgot to propose the interface of the policy: alternative -
> 1) bool TerminationPolicy::operator(), where 'true' means terminate.
> 2) bool TerminationPolicy::terminate(), true means terminate
> 3) bool TerminationPolicy::keep_running(), true means not to terminate.
>

This looks plausible to me. (I think the whole idea for this API is not=20
useful and I would not use it or want it in the Standard, but I think=20
you're thinking about decent library design issues at this point.)
Rather than immediately asking for input on the idea in the context of a=20
"future proposal", why don't you take your API above and build it into a=20
repository (say, on GitHub) providing your algorithms in the form of a=20
header file "limited_algorithm.h"?  And then see if "limited_algorithm.h"=
=20
is actually useful in your work?  This will help flush out any design=20
issues you may be missing, and has the super benefit of contributing to the=
=20
community (assuming you add a permissive enough LICENSE to your work =E2=80=
=94 MIT,=20
Boost, whatever).

After you've written `distance_n`, I agree with Nicol that `lower_bound_n`=
=20
should be the next thing you should target, in order to flush out your=20
design issues the fastest.

HTH,
Arthur

--=20
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 e=
mail 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/20cb2f02-3f3e-4384-af86-3d7691fde98a%40isocpp.or=
g.

------=_Part_7506_1560310572.1530222692192
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, June 27, 2018 at 9:31:22 AM UTC-7, Daniel Gu=
tson 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">On=
 Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson <span dir=3D"ltr">&lt;<a targe=
t=3D"_blank" gdf-obfuscated-mailto=3D"apYsSh_kCAAJ" rel=3D"nofollow">daniel=
....@gmail.com</a>&gt;</span> wrote:<br><div><div class=3D"gmail_quote"><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c=
cc solid;padding-left:1ex"><div dir=3D"ltr">On Wed, Jun 27, 2018 at 1:18 PM=
, Nicol Bolas <span dir=3D"ltr">&lt;<a target=3D"_blank" gdf-obfuscated-mai=
lto=3D"apYsSh_kCAAJ" rel=3D"nofollow">jmck...@gmail.com</a>&gt;</span> wrot=
e:<br><div><div class=3D"gmail_quote"><span><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex"><div dir=3D"ltr">On Wednesday, June 27, 2018 at 12:06:00=
 PM UTC-4, Daniel Gutson wrote:<span><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex"><div dir=3D"ltr"><div><div class=3D"gmail_quote">On Wed, Jun 27=
, 2018 at 12:59 PM, Nicol Bolas <span dir=3D"ltr">&lt;<a rel=3D"nofollow">j=
mck...@gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex"><div dir=3D"ltr"><span>On Wednesday, June 27, 2018 at 11:4=
7:50 AM UTC-4, Daniel Gutson wrote:<blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"ltr">Some functions may keep looping for an unbounde=
d amount of iterations, such as std::distance. This may cause DoS.<div>I pr=
opose to add *_n versions so things are controlled in case of invalid input=
..<br clear=3D"all"></div></div></blockquote><div><br></div></span><div>1. W=
hat does a function return if it reached `n`? Is that considered to produce=
 a correct iterator, or are you just catching invalid input? If it&#39;s th=
e latter, then I imagine some form of exception would be thrown. Is that wh=
at we want?<br></div></div></blockquote><div><br></div><div>I want to surve=
y the idea at high level first, then we can dig into the implementation, ex=
pected behavior, interface.</div></div></div></div></blockquote><div><br></=
div></span><div>Without considering expected behavior, the idea cannot reas=
onably be considered at the high level. If the caller cannot tell the diffe=
rence between early termination and the getting a legitimate distance `dist=
ance_n`, then that will strongly affect who will and will not use this func=
tion. If it&#39;s not considered valid behavior, then it changes how users =
have to interact with it, which again affects who will and will not be will=
ing to call it.</div><div><br></div><div>So yes, these are things that must=
 be considered, even from a high level. They affect the usability of the to=
ol. And since this tool exists purely for safety reasons, then such usabili=
ty needs to be taken into account. There&#39;s no point in having &quot;saf=
e&quot; interfaces nobody is willing to use, after all.</div><span><div><br=
></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;=
border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><=
div><div class=3D"gmail_quote"><div></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex"><div dir=3D"ltr"><div></div><div></div><div>2. What is an =
appropriate &quot;n&quot; for detecting invalid input for a particular rang=
e, and how do you communicate that value to those who directly call `std::d=
istance_n` or similar functions? After all, `std::distance` and the like ar=
e usually used deep down in various systems; even if they were using `dista=
nce_n`, how would you tell them what the right &quot;n&quot; is?</div></div=
></blockquote><div><br></div><div>There are two non-mutually-exclusive appr=
oaches about this.</div><div>1- iteration limit</div><div>1.1 - based on kn=
own boundaries (e.g. memory space knowlege)</div><div>1.2 - based on measur=
ements</div><div>1.2.1 - experimentally determined</div><div>1.2.2 - run-ti=
me determined based on running statistics</div><div>2- time limit</div><div=
><br></div><div>Maybe a better interface (discussion I&#39;d like to postpo=
ne a little bit after getting more consensus) could be to accept a caller-p=
rovided termination_policy, and offer 3 basic policies (count-based, time-b=
ased, and an OR-combining policy).</div></div></div></div></blockquote><div=
><br></div></span><div>It doesn&#39;t matter what the information is. I wan=
t to know how you get that information from the high-level code that suppli=
ed the potentially invalid iterators (and therefore is the code that has so=
me idea of what such boundary conditions ought to be) to the low-level code=
 that will actually call `std::distance` (which probably has no idea what a=
 reasonable boundary is).<br></div><div><br></div><div>Take `std::lower_bou=
nd`. It probably uses `std::advance` or `std::next`, which would have simil=
ar boundary condition functions. `lower_bound` has <i>no idea</i> what a re=
asonable boundary condition would be; only the caller would know. So do we =
now need a version of `lower_bound` that takes this boundary condition as a=
n optional parameter?<br></div></div></blockquote><div><br></div><div><br><=
/div></span><div>namespace std {</div><div><br></div><div><div>template&lt;=
 class InputIt<b>, class TerminationPolicy</b> &gt;</div><div>constexpr <b>=
std::optional&lt;</b>typename std::iterator_traits&lt;InputIt&gt;:<wbr>:dif=
ference_type<b>&gt;</b>=C2=A0</div><div>=C2=A0 =C2=A0 distance( InputIt fir=
st, InputIt last, <b>TerminationPolicy&amp;&amp; terminationPolicy</b> );</=
div></div><div>=C2=A0</div><div>}</div><div><br></div><div>I&#39;m using &#=
39;optional&#39; but could be &#39;expected&#39; or &#39;outcome&#39; depen=
ding on their progress (I&#39;m not up to date about them).</div><div><br><=
/div><div>How does that look?</div></div></div></div></blockquote><div><br>=
</div><div>I forgot to propose the interface of the policy: alternative -</=
div><div>1) bool <span style=3D"font-size:small;background-color:rgb(255,25=
5,255);float:none;display:inline">TerminationPolicy::</span>operator(), whe=
re &#39;true&#39; means terminate.</div><div>2) bool TerminationPolicy::ter=
minate()<wbr>, true means terminate</div><div>3) bool=C2=A0<span style=3D"f=
ont-size:small;background-color:rgb(255,255,255);float:none;display:inline"=
>TerminationPolicy::keep_<wbr>running(), true means not to terminate.</span=
></div></div></div></div></blockquote><div><br></div><div>This looks plausi=
ble to me. (I think the whole idea for this API is not useful and I would n=
ot use it or want it in the Standard, but I think you&#39;re thinking about=
 decent library design issues at this point.)</div><div>Rather than immedia=
tely asking for input on the idea in the context of a &quot;future proposal=
&quot;, why don&#39;t you take your API above and build it into a repositor=
y (say, on GitHub) providing your algorithms in the form of a header file &=
quot;limited_algorithm.h&quot;? =C2=A0And then see if &quot;limited_algorit=
hm.h&quot; is actually useful in your work? =C2=A0This will help flush out =
any design issues you may be missing, and has the super benefit of contribu=
ting to the community (assuming you add a permissive enough LICENSE to your=
 work =E2=80=94 MIT, Boost, whatever).</div><div><br></div><div>After you&#=
39;ve written `distance_n`, I agree with Nicol that `lower_bound_n` should =
be the next thing you should target, in order to flush out your design issu=
es the fastest.</div><div><br></div><div>HTH,</div><div>Arthur</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/20cb2f02-3f3e-4384-af86-3d7691fde98a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/20cb2f02-3f3e-4384-af86-3d7691fde98a=
%40isocpp.org</a>.<br />

------=_Part_7506_1560310572.1530222692192--

------=_Part_7505_782932071.1530222692191--

.