Re: [lmi] Is bourn_cast demonstrably correct? (+PATCH)

[Greg Chicares]

On 2017-03-20 18:44, Vadim Zeitlin wrote:
> On Mon, 20 Mar 2017 02:22:22 +0000 Greg Chicares <address@hidden> wrote:
> 
> ..detailed argument about bourn_cast correctness snipped...
> GC> I speculate that this argument can be faithfully summarized by saying
> GC> that for integer comparison to behave counterintuitively, the types
> GC> must be of different signednesses and one must be negative, but there
> GC> is no path through the code where that can happen.
> 
>  Yes, I agree with your analysis and I had initially done the same one,
> albeit much less rigorously, to convince myself that this code is indeed
> correct.

Thanks for reading it. I wish I could have made it shorter.

>  It still somewhat bothers me, however, to see "from < 0" comparison for a
> possibly unsigned or not signed type though

I had thought of imbuing it with an appropriate signedness, but couldn't
convince myself that the extra complication would be worthwhile. However...

> and, worse, it bothers g++ 6 as
> well:
> 
> bourn_cast.hpp:87:65: error: comparison of constant ‘0’ with boolean 
> expression is always false [-Werror=bool-compare]

...I didn't get that warning here, and of course we don't want it anywhere.

> This can, of course, be easily fixed by disabling the warning and the
> attached patch does it. If we decide to not do anything else, could you
> please apply it to allow me to build the test suite with gcc 6 here?

Absolutely. If gcc-4.9.2 complains that it doesn't know that warning,
I'll conditionalize it.

>  But ideally I'd still like to find a way to write all these tests without
> comparing types of different signedness (which is a common mistake in C and
> C++ and the reason for "-Wsign-compare" existence). This would allow
> avoiding disabling the warning and could also make the code even more
> obviously correct.

I had (casually) thought of attempting that, but I guess that it would
be rather difficult, at least with C++11. As it is, I think we can
sequester all instances of this warning in this one file, and use a
pragma to suppress them only here. Still, it would be really neat to
write code that wouldn't give the warning at all.

> Unfortunately I don't think it's going to be simple to
> do it in C++11. In C++17 we could write something like this:
[...]
>     if constexpr(from_traits::is_signed)
>         {
>         if constexpr(to_traits::is_signed)
>             {
>             if(from < to_traits::lowest())
>                 throw std::runtime_error("Cast would transgress lower 
> limit.");
>             }
>         else
>             {
>             if(from < 0)
>                 throw std::runtime_error("Cast would convert negative to 
> unsigned.");
>             }

Recently I posted an experimental patch that I think did something
similar:
  http://lists.nongnu.org/archive/html/lmi/2017-03/msg00101.html
+    static constexpr To lower_bound = to_traits::lowest();
+    static constexpr To upper_bound = to_traits::max();
+    static constexpr bool must_test_lower = from_traits::lowest() < 
lower_bound;
+    static constexpr bool must_test_upper = upper_bound < from_traits::max();
-    if(! to_traits::is_signed && from < 0)
+    if(to_is_unsigned && from_is_signed && from < 0)
         throw std::runtime_error("Cast would convert negative to unsigned.");

Would that technique work as well (without warnings) as your C++17
suggestion above? I don't believe I tested it without the #pragma
to suppress warnings with my C++11 compiler; I'll try that later.
I guess it wouldn't: yours has more conditions, from which the
compiler can prove that it's not comparing signed and unsigned.

I'm juggling opposing forces here. Keeping the code tiny makes it
easier to understand, and its correctness easier to show. But OTOH
preventing compiler warnings (and even possibly making it faster in
some cases) is worth some amount of complexity. And actually it may
be easier to prove the correctness of your longer code: any proof
"forks" at each possibility of signed-unsigned comparison, causing
a very limited combinatorial explosion; if you're just translating
a proof into code, then the proof can be read directly from the
code (and the compiler can verify at least the consistency of the
type-algebra), so maybe it's actually easier to see that the longer
code is correct. I'll have to sleep on it.

> (also requires #including <type_traits> to actually compile) and personally
> I think I prefer this, in spite of it being longer (partly due to some
> redundancy that could be avoided by the use of a helper function), to the
> original version. But to translate this in C++11 we'd need several helper
> functions and I don't think the result would be especially clear. OTOH we
> still would at least be able to avoid disabling the warning, which is nice.
> Do you think it would make sense to attempt to translate the approach above
> to C++11 or do you dislike its verbosity so much that I shouldn't even
> bother with doing this?

Are helper functions strictly necessary, or would helper type-aliases
and helper-variables be enough? I ask because I suspect they'd be
easier to read than functions.

BTW, let me share my short-term plans for this facility. First, I asked
myself whether it should just forbid floating point; the answer is no,
because we really do have code that converts double to integral types
using value_cast<>(), and the whole point of bourn_cast<>() is to
replace boost::numeric_cast<>() in value_cast<>(). Then I asked myself
how hard it would be to accommodate floating types correctly, and my
initial conclusion is that it shouldn't be hard. Tentatively I conclude
that...

- We can use bourn_cast as it is for conversion from any arithmetic
type to an integral type. A floating "From" type should behave like an
imprecise but very wide signed integral type.

- We can add just a little code inside the present function template to
take care of conversion from arithmetic type to floating type. Here's
a draft that I haven't even tried to compile yet:

    if(!to_traits::is_integer)
        {
        static_assert(to_traits::is_iec_559);
        return
              std::isnan(value))            ?  to_traits::quiet_NaN
            : (to_traits::max() < value)    ?  to_traits::infinity
            : (value < to_traits::lowest()) ? -to_traits::infinity
            : static_cast<To>(from);
        }

That's intended to be strictly correct. In practice, it may be better
(faster) to replace the ternary-statement chain with
  return static_cast<To>(from);
for any compiler that passes all the (not yet written) unit tests.

I tried figuring out how to make it strictly correct even if is_iec_559
is false, but that way lies madness, and I don't have a VAX to test it
on anyway. I don't know why anything like this surprised me anymore, but
I was surprised to learn that standard C++ doesn't provide a portable
way to produce a negative infinity. But there's hardly a more trustworthy
source than Plauger:
  https://groups.google.com/d/msg/comp.std.c++/oFdAC-DDGKU/06D5IXv3zYsJA
who says the C++ committee wanted to defer to the IEC 559 people.