Define behavior for over/underflow in vim script arithmetic

[James McCoy]

Hi all,

Recently, there was some work done on defining how to handle converting
numeric literals in vim script to C integers -- basically, clamp to the
extremes of the datatype. If it would exceed the max/min value, then
just treat it as the max/min value.

However, there's nothing defining how arithmetic behaves when it would
exceed the range of the datatype. The only information in the help is:

Number A 32 or 64 bit signed number. |expr-number| *Number*
64-bit Numbers are available only when compiled with the
|+num64| feature.

Now, in C signed over/underflow is undefined behavior. If you're "lucky",
the implementation will wrap but it could just as well optimize the code
under the assumption that the code can't over/underflow.

Currently, Vim runs afoul of undefined behavior as can easily be seen
with a -fsanitize=undefined build by running

if has('num64')
echo float2nr(pow(2, 62)) * 2
else
echo float2nr(pow(2, 30)) * 2
endif

It would be nice for there to be defined behavior here for the user,
instead of exposing them to the whims of the compiler implementation.

Cheers,
--
James
GPG Key: 4096R/91BF BF4D 6956 BD5D F7B7 2D23 DFE6 91AE 331B A3DB

[Bram Moolenaar]

James McCoy wrote:

> Recently, there was some work done on defining how to handle converting
> numeric literals in vim script to C integers -- basically, clamp to the
> extremes of the datatype. If it would exceed the max/min value, then
> just treat it as the max/min value.
>
> However, there's nothing defining how arithmetic behaves when it would
> exceed the range of the datatype. The only information in the help is:
>
> Number A 32 or 64 bit signed number. |expr-number| *Number*
> 64-bit Numbers are available only when compiled with the
> |+num64| feature.
>
> Now, in C signed over/underflow is undefined behavior. If you're "lucky",
> the implementation will wrap but it could just as well optimize the code
> under the assumption that the code can't over/underflow.

Yeah, I consider this a bug in the C standard. Undefined behavior is
useless, the only reason I suspect this is done is so that compiler
writers can makey the code < 1% faster. And at the same time require
programmers to handle all the edge cases, which gets really complicated
and everybody forgets about.

> Currently, Vim runs afoul of undefined behavior as can easily be seen
> with a -fsanitize=undefined build by running
>
> if has('num64')
> echo float2nr(pow(2, 62)) * 2
> else
> echo float2nr(pow(2, 30)) * 2
> endif
>
> It would be nice for there to be defined behavior here for the user,
> instead of exposing them to the whims of the compiler implementation.

Unfortunately, that is quite difficult. I propose the compiler standard
gets fixed. This means only the few compilers that exist need to take
care of this, instead of the millions of C programs.

--
Every person is responsible for the choices he makes.

/// Bram Moolenaar -- Br...@Moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///

[Nikolay Aleksandrovich Pavlov]

2017-05-05 23:23 GMT+03:00 Bram Moolenaar <Br...@moolenaar.net>:
>
> James McCoy wrote:
>
>> Recently, there was some work done on defining how to handle converting
>> numeric literals in vim script to C integers -- basically, clamp to the
>> extremes of the datatype. If it would exceed the max/min value, then
>> just treat it as the max/min value.
>>
>> However, there's nothing defining how arithmetic behaves when it would
>> exceed the range of the datatype. The only information in the help is:
>>
>> Number A 32 or 64 bit signed number. |expr-number| *Number*
>> 64-bit Numbers are available only when compiled with the
>> |+num64| feature.
>>
>> Now, in C signed over/underflow is undefined behavior. If you're "lucky",
>> the implementation will wrap but it could just as well optimize the code
>> under the assumption that the code can't over/underflow.
>
> Yeah, I consider this a bug in the C standard. Undefined behavior is
> useless, the only reason I suspect this is done is so that compiler
> writers can makey the code < 1% faster. And at the same time require
> programmers to handle all the edge cases, which gets really complicated
> and everybody forgets about.

“Undefined behaviour” allows using one and the same standard on a
bunch of incompatible systems. E.g. you cannot define the result of a
signed integer overflow if one system you target for is using one’s
complement and another is using two’s complement: either in one case
or another you will end up with much more then 1% slowdown of integer
operations.

Though it would be probably better to make the standard modular,
splitting away implementation-specific details and making them defined
on per-architecture basis, additionally allowing programmers to state
“I want *that* behaviour, ready to deal with the slowdown myself”.

You may want to thank C authors that they have not chosen to support
ternary system as well, with the same standard. Though I do not think
C would be popular in this case.

>
>> Currently, Vim runs afoul of undefined behavior as can easily be seen
>> with a -fsanitize=undefined build by running
>>
>> if has('num64')
>> echo float2nr(pow(2, 62)) * 2
>> else
>> echo float2nr(pow(2, 30)) * 2
>> endif
>>
>> It would be nice for there to be defined behavior here for the user,
>> instead of exposing them to the whims of the compiler implementation.
>
> Unfortunately, that is quite difficult. I propose the compiler standard
> gets fixed. This means only the few compilers that exist need to take
> care of this, instead of the millions of C programs.
>
> --
> Every person is responsible for the choices he makes.
>
> /// Bram Moolenaar -- Br...@Moolenaar.net -- http://www.Moolenaar.net \\\
> /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
> \\\ an exciting new programming language -- http://www.Zimbu.org ///
> \\\ help me help AIDS victims -- http://ICCF-Holland.org ///
>

> --
> --
> You received this message from the "vim_dev" maillist.
> Do not top-post! Type your reply below the text you are replying to.
> For more information, visit http://www.vim.org/maillist.php
>
> ---
> You received this message because you are subscribed to the Google Groups "vim_dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to vim_dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[R0b0t1]

On Fri, May 5, 2017 at 3:23 PM, Bram Moolenaar <Br...@moolenaar.net> wrote:
>
> James McCoy wrote:
>
>> Recently, there was some work done on defining how to handle converting
>> numeric literals in vim script to C integers -- basically, clamp to the
>> extremes of the datatype. If it would exceed the max/min value, then
>> just treat it as the max/min value.
>>
>> However, there's nothing defining how arithmetic behaves when it would
>> exceed the range of the datatype. The only information in the help is:
>>
>> Number A 32 or 64 bit signed number. |expr-number| *Number*
>> 64-bit Numbers are available only when compiled with the
>> |+num64| feature.
>>
>> Now, in C signed over/underflow is undefined behavior. If you're "lucky",
>> the implementation will wrap but it could just as well optimize the code
>> under the assumption that the code can't over/underflow.
>
> Yeah, I consider this a bug in the C standard. Undefined behavior is
> useless, the only reason I suspect this is done is so that compiler
> writers can makey the code < 1% faster. And at the same time require
> programmers to handle all the edge cases, which gets really complicated
> and everybody forgets about.
>

There's reasons to want other behavior, and if the standard specified
anything in this case it would limit the hardware that compliant C
could run on. In almost every case where there is undefined behavior,
that previous reason is precisely why it is left unspecified. That
most instruction sets and compilers implement wrapping arithmetic is
irrelevant - should C implement features that require an IOMMU, just
because you're unaware of anybody who would want to avoid the use of
one?

As an example, saturating arithmetic requires nonwrapping mathematical
operations (https://en.wikipedia.org/wiki/Saturation_arithmetic). The
SEI CERT C Coding Standard has a section on arithmetic,
https://securecoding.cert.org/confluence/pages/viewpage.action?pageId=270,
of which rule "INT30-C" is notable: "Ensure that unsigned integer
operations do not wrap."

There are also algorithms that make use of saturating arithmetic, and
numerical methods that might wish to trap on overflow or underflow.


It seems to be the vogue for FOSS software authors to have strong
opinions, but frankly this one makes you look like an idiot.

>> Currently, Vim runs afoul of undefined behavior as can easily be seen
>> with a -fsanitize=undefined build by running
>>
>> if has('num64')
>> echo float2nr(pow(2, 62)) * 2
>> else
>> echo float2nr(pow(2, 30)) * 2
>> endif
>>
>> It would be nice for there to be defined behavior here for the user,
>> instead of exposing them to the whims of the compiler implementation.
>
> Unfortunately, that is quite difficult. I propose the compiler standard
> gets fixed. This means only the few compilers that exist need to take
> care of this, instead of the millions of C programs.
>

That is never going to happen. The choice here is to either implement
correct arithmetic or leave it exposed. Since most people are
expecting it it's entirely possible to suggest no action is necessary,
but if anyone has the time it would be one of the many steps necessary
to making safer and less error prone programs more common.

Implementing it is, in theory, easy, as over and underflow can be
trapped, but last I checked the support for this in GCC was
nonfunctional for some reason. The relevant options are here:
https://gcc.gnu.org/onlinedocs/gcc-4.0.2/gcc/Code-Gen-Options.html as
"-ftrapv" and "-fwrapv". On most architectures this is implemented as
a software trap. The proper way to solve this is in hardware.

It's kind of sad, really; the DoD (among other parties) has spent
hundreds of thousands of dollars, if not millions of dollars,
researching "safe arithmetic" due to faulty hardware implementations.

[Bram Moolenaar]

James McCoy wrote:

> >> Recently, there was some work done on defining how to handle converting
> >> numeric literals in vim script to C integers -- basically, clamp to the
> >> extremes of the datatype. If it would exceed the max/min value, then
> >> just treat it as the max/min value.
> >>
> >> However, there's nothing defining how arithmetic behaves when it would
> >> exceed the range of the datatype. The only information in the help is:
> >>
> >> Number A 32 or 64 bit signed number. |expr-number| *Number*
> >> 64-bit Numbers are available only when compiled with the
> >> |+num64| feature.
> >>
> >> Now, in C signed over/underflow is undefined behavior. If you're "lucky",
> >> the implementation will wrap but it could just as well optimize the code
> >> under the assumption that the code can't over/underflow.
> >
> > Yeah, I consider this a bug in the C standard. Undefined behavior is
> > useless, the only reason I suspect this is done is so that compiler
> > writers can makey the code < 1% faster. And at the same time require
> > programmers to handle all the edge cases, which gets really complicated
> > and everybody forgets about.
>
> “Undefined behaviour” allows using one and the same standard on a
> bunch of incompatible systems. E.g. you cannot define the result of a
> signed integer overflow if one system you target for is using one’s
> complement and another is using two’s complement: either in one case
> or another you will end up with much more then 1% slowdown of integer
> operations.

Nearly all CPUs use two's compliment and overflow is very well defined.
If there are some (embedded CPUs) that behave differently they should
use another standard. Of course companies don't like that, because they
have to admit they don't implement the "normal" C standard. This is
a political choice, not a technical one.

> Though it would be probably better to make the standard modular,
> splitting away implementation-specific details and making them defined
> on per-architecture basis, additionally allowing programmers to state
> “I want *that* behaviour, ready to deal with the slowdown myself”.
>
> You may want to thank C authors that they have not chosen to support
> ternary system as well, with the same standard. Though I do not think
> C would be popular in this case.

The C language was originally made for a wide range of CPU, even weird
ones. Now that 99.9% of computers are fairly standard it would be a bad
idea to suffer from supporting those conrder cases.

Compilers could also support a flag to "define" that "undefined"
behavior, garanteeing the outcome, and perhaps suffering a tiny bit in
optimization.

--
It is illegal for a driver to be blindfolded while operating a vehicle.
[real standing law in Alabama, United States of America]

[Bram Moolenaar]

Of course it is not irrelevant. Behavior of arithmethics must be
predictable. Otherwise switching compiler might break your program
(unless you teadiously find all places where that undefined behavior
occurs and add quite a bit of hard to understand code to work around it).

> As an example, saturating arithmetic requires nonwrapping mathematical
> operations (https://en.wikipedia.org/wiki/Saturation_arithmetic). The
> SEI CERT C Coding Standard has a section on arithmetic,
> https://securecoding.cert.org/confluence/pages/viewpage.action?pageId=270,
> of which rule "INT30-C" is notable: "Ensure that unsigned integer
> operations do not wrap."
>
> There are also algorithms that make use of saturating arithmetic, and
> numerical methods that might wish to trap on overflow or underflow.

Never heard of it, so I would argue that for the average C programmer
this is irrelevant. Keep in mind that C is a production language, not
some scientific experiment. Programmers must be productive.

> It seems to be the vogue for FOSS software authors to have strong
> opinions, but frankly this one makes you look like an idiot.

Sure, I have only programmed in C for more than 30 years, I know
nothing.

> >> Currently, Vim runs afoul of undefined behavior as can easily be seen
> >> with a -fsanitize=undefined build by running
> >>
> >> if has('num64')
> >> echo float2nr(pow(2, 62)) * 2
> >> else
> >> echo float2nr(pow(2, 30)) * 2
> >> endif
> >>
> >> It would be nice for there to be defined behavior here for the user,
> >> instead of exposing them to the whims of the compiler implementation.
> >
> > Unfortunately, that is quite difficult. I propose the compiler standard
> > gets fixed. This means only the few compilers that exist need to take
> > care of this, instead of the millions of C programs.
>
> That is never going to happen. The choice here is to either implement
> correct arithmetic or leave it exposed. Since most people are
> expecting it it's entirely possible to suggest no action is necessary,
> but if anyone has the time it would be one of the many steps necessary
> to making safer and less error prone programs more common.
>
> Implementing it is, in theory, easy, as over and underflow can be
> trapped, but last I checked the support for this in GCC was
> nonfunctional for some reason. The relevant options are here:
> https://gcc.gnu.org/onlinedocs/gcc-4.0.2/gcc/Code-Gen-Options.html as
> "-ftrapv" and "-fwrapv". On most architectures this is implemented as
> a software trap. The proper way to solve this is in hardware.

If you just implement 2's complement arithmethic, which nearly all CPUs
do, the only thing to do is document it.

> It's kind of sad, really; the DoD (among other parties) has spent
> hundreds of thousands of dollars, if not millions of dollars,
> researching "safe arithmetic" due to faulty hardware implementations.

Instead of fixing the hardware? The good old "we'll fix it in
software". Anyway, hardly any government is good with IT, most are a
complete failure when it comes to making good decisions. Best is to get
people who daily use the language, they know how it should work.

--
It is illegal for anyone to try and stop a child from playfully jumping over
puddles of water.
[real standing law in California, United States of America]

[James McCoy]

On Fri, May 05, 2017 at 10:23:49PM +0200, Bram Moolenaar wrote:
> James McCoy wrote:
> > It would be nice for there to be defined behavior here for the user,
> > instead of exposing them to the whims of the compiler implementation.
>
> Unfortunately, that is quite difficult. I propose the compiler standard
> gets fixed. This means only the few compilers that exist need to take
> care of this, instead of the millions of C programs.

Since that's unlikely to happen, how about fixing it in one editor
instead of passing it off to all the Vim users?

[R0b0t1]

I'd like to suggest that people make choices for reasons. If you're
unable to spend what is likely to be an amount of time equal to what
they spent originally understanding their problem understanding their
problem, you don't really have any room to criticize their solution.

Do I know of any processors that actually implement one's arithmetic?
No. Do I know any that implement strange arithmetic that the C
standard body could easily make incompatible with C by tightening the
standards? Yes, I gave some. And note per my other reply before this
that wrapping arithmetic generally isn't what is wanted anyway, and
needs constant workarounds to help secure code.

>> Though it would be probably better to make the standard modular,
>> splitting away implementation-specific details and making them defined
>> on per-architecture basis, additionally allowing programmers to state
>> “I want *that* behaviour, ready to deal with the slowdown myself”.
>>
>> You may want to thank C authors that they have not chosen to support
>> ternary system as well, with the same standard. Though I do not think
>> C would be popular in this case.
>
> The C language was originally made for a wide range of CPU, even weird
> ones. Now that 99.9% of computers are fairly standard it would be a bad
> idea to suffer from supporting those conrder cases.
>
> Compilers could also support a flag to "define" that "undefined"
> behavior, garanteeing the outcome, and perhaps suffering a tiny bit in
> optimization.
>

99.9% of computers aren't fairly standard at all, because that number
still includes microcontrollers. If you look at any given vendor there
are bound to be a slew of products that have extremely novel (well,
sometimes) pieces of hardware attached to the processor on die. While
most of them are accessed by memory mapped registers some are so
integrated into the flow control of the main core that the C standard
makes exceptions (see the floating point part of the standard, though
I admit most of it is now a historical curiosity).

[R0b0t1]

On Sat, May 6, 2017 at 8:45 PM, James McCoy <jame...@jamessan.com> wrote:
> On Fri, May 05, 2017 at 10:23:49PM +0200, Bram Moolenaar wrote:
>> James McCoy wrote:
>> > It would be nice for there to be defined behavior here for the user,
>> > instead of exposing them to the whims of the compiler implementation.
>>
>> Unfortunately, that is quite difficult. I propose the compiler standard
>> gets fixed. This means only the few compilers that exist need to take
>> care of this, instead of the millions of C programs.
>
> Since that's unlikely to happen, how about fixing it in one editor
> instead of passing it off to all the Vim users?
>

I'm willing to help implement it. Unfortunately, the most
straightforward solution, using `-ftrapv` and catching the resulting
SIGABRT when overflow occurs, suffers from a bug in GCC dating from
'08: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35412. `-ftrapv`
does seem to work in the current release of Cygwin, but did not work
last I tried it on Linux.

A possible workaround is the combination of `-fsanitize=undefined`,
`-fsanitize=signed-integer-overflow`, and
`-fsanitize-undefined-trap-on-error`. The last flag given does not
seem to be documented. When it is used to compile a test program under
Cygwin and that program executed I receive an illegal instruction core
dump. I have yet to test it on a GNU/Linux toolchain.

```
#include <signal.h>
#include <stdio.h>
#include <limits.h>

void
handler(int signum)
{
printf("Overflow detected.\n");
}

int
main(int argc, char *argv[])
{
int i = INT_MAX;
signal(SIGABRT, &handler);
i++;

return 0;
}
```

`gcc -ftrapv`
`gcc --fsanitize=undefined -fsanitize=signed-integer-overflow
-fsanitize-undefined-trap-on-error`

[Christian Brabandt]

So what would you suggest to implement a sane behaviour?

Best,
Christian
--
Das Vorurteil ist ein Floß, an das sich der schiffbrüchige Geist
klammert und ins Sichere rudert.
-- Ben Hecht

[R0b0t1]

That depends. The OP's title merely references defining the behavior.
Vimscript could be defined to have wrapping arithmetic operations and
this discussion would then be over.

The other option, which seems like it is more in the spirit of the
body of the original post, and which eliminates the word "undefined"
per the C standard, involves trapping integer overflow and underflow
or ensuring overflow or underflow never occurs. This can be done in
the following ways:

1) For some POSIX systems using GCC, it might be necessary to wait
until the bug with "-ftrapv" is fixed and and the patch distributed.
2) For some POSIX systems using GCC nothing needs to be done and
"-ftrapv" is usable.
3) For all(?) POSIX systems the combination of "-fsanitize=undefined
-fsanitize=signed-integer-overflow -fsanitize-undefined-trap-on-error"
works despite "-ftrapv" not working.
4) For Windows it is possible to generate an SEH exception on overflow
or underflow, however I'm not sure what other facilities expose this
functionality.
5) For all supported systems explicit range checks could be done for
vimscript arithmetic.
6) For all supported systems a large number library could be used to
eliminate the possibility of overflow or underflow.

With respect to the combination of 1, 2, and 3, some reading on the
issue (http://blog.robertelder.org/gcc-signed-overflow-trapping-ftrapv-doesnt-work/)
implies that newer versions of GCC might not suffer from the "-ftrapv"
problem. It may be a better idea to use the flags given in item 3
anyway, as they seem to be newer; unfortunately that generates SIGILL
instead of SIGABRT and I can't find a way to recover from that signal
in a portable way.

My only comment on 4 is that some programs are unable to use SEH, and
vim is likely among them, but someone else would have to comment.

5 and 6 are likely the most work, but also provide the most
flexibility. 6 might eventually be a goal anyway, but I'm not aware of
anyone having problems with the range of the datatypes in vimscript.


That still leaves the question of what happens when overflow or
underflow occurs. If overflow and underflow are disallowed, clamping
the value and continuing execution is the only choice I'm aware of
that doesn't involve throwing an exception or halting execution - not
that those are unreasonable choices.

As to implementation, the first three (or four) items would require
creating the signal handler and exposing the vimscript interpreter
internals to it. Comments on the best way to do that are very welcome,
I'm not too familiar with the Vim codebase. Five would simply involve
adding the range checks manually and reporting an error (or clamping
the values) when exceptional arithmetic occurs.


Or, *instead of all of the above,* arithmetic can be defined to wrap.
Technically, with no other changes, this doesn't solve the original
complaint about undefined behavior - as it is left undefined in the C
standard, Vim could conceivably be ported to a system which does wrap
exceptional arithmetic by default.

[R0b0t1]

Apologies for the follow-up post. I could help with the backend but I
have next to no idea of how to properly interface it with vim. If that
expertise never materializes, or it seems more expedient to keep the
behavior as it is now, it might be worth adding a definitive statement
near the area of the documentation quote in the original post, and
making sure the behavior in the engine is commented so that it is
clear that this behavior, when obtained in C with only built in
arithmetic, is undefined.

This might seem silly but a lot of persistent problems in Unix
projects are due to a history of relying on "that will always be the
default!" undefined behavior.

[James McCoy]

On Mon, May 08, 2017 at 03:08:31PM -0500, R0b0t1 wrote:
> Or, *instead of all of the above,* arithmetic can be defined to wrap.
> Technically, with no other changes, this doesn't solve the original
> complaint about undefined behavior

It would, because it would be defined to wrap. That's trivial to
implement with GCC by building with `-fwrapv`, but I'm not sure how many
other compilers provide a similar flag.

[R0b0t1]

On Mon, May 8, 2017 at 6:24 PM, James McCoy <jame...@jamessan.com> wrote:
> On Mon, May 08, 2017 at 03:08:31PM -0500, R0b0t1 wrote:
>> Or, *instead of all of the above,* arithmetic can be defined to wrap.
>> Technically, with no other changes, this doesn't solve the original
>> complaint about undefined behavior
>
> It would, because it would be defined to wrap. That's trivial to
> implement with GCC by building with `-fwrapv`, but I'm not sure how many
> other compilers provide a similar flag.
>

The distinction I meant to point out is that the implementation wraps
the arithmetic, but if it doesn't you would have to do it yourself if
the code aims to be portable.

Per the documentation: "This option instructs the compiler to assume
that signed arithmetic overflow of addition, subtraction and
multiplication wraps around using twos-complement representation."

It doesn't implement wrapping arithmetic, it just assumes that
arithmetic does wrap.

[Bram Moolenaar]

You can try it, but I suspect there are several places we depend on
overflow to work normally. Esp. in the encryption code (it has a
runtime test to check that this works).

--
<Beeth> Girls are like internet domain names,
the ones I like are already taken.
<honx> Well, you can stil get one from a strange country :-P