Re: [boost] [safe_numerics] Review Part 2 (Implementation)

Subject: Re: [boost] [safe_numerics] Review Part 2 (Implementation)
From: Robert Ramey (ramey_at_[hidden])
Date: 2017-03-07 17:32:05

I've spent a lot of time going over this and have incorporated changes
to address most of the points.  There are still some things I'm working
on though.

I think the major problem is confusion about what promotion policy
should do and what should the requirements on the types it accepts.
Factoring out the promotion policy is necessary to keep things
sort of understandable and keeping safe operations from turning into
a huge ball of spagetti.  In retrospect, I'm beginning to wonder
of automatic type promotion was a great idea.  In any event, this
will take me a couple of more days to sort through.

I've also incorporated almost all your observations of documentation.

I must say that I'm in awe of your abilities to read through and
understand 6000 lines of C++ template code, 1000 lines of examples, and
52 pages of documentation (when rendered as a pdf) in such a short
time.  I spend a long, long time developing this, and I dare say
I think you already understand it better than I do.  Clearly
we have different brain structure - I guess that's a good thing.

I have to say I love Boost.

Robert Ramey

On 3/6/17 7:35 AM, Steven Watanabe via Boost wrote:
> AMDG
>
> All comments are as of 3bcfabe1cafb8ef6edf08d3bd8730a1555b1c45d
>
> automatic.hpp
>
> 15:
> // policy which creates results types equal to that of C++ promotions.
> // Using the policy will permit the program to build and run in release
> // mode which is identical to that in debug mode except for the fact
> // that errors aren't trapped.
> Copy/paste from native?

Right
>
> 83:
>         // clause 2 - otherwise if the rank of the unsigned type exceeds
>         // the rank of the of the maximum signed type
> How is this possible?The rank of std::intmax_t
> is the maximum possible rank.  If the unsigned type
> is larger, then rank will return void which gives
> a compile error when accessing ::value.

I changed this.

> Actually it looks like calculate_max_t was originally
> written to return T or U, but was then altered to
> use [u]intmax_t.

Right - My intention was that the automatic would reflect
the standard C++ promotions but would return the
[u]intmax_t .  This is later reduced according to
the anticipated range of the result.  So the whole
business is about trying to get the sign right.

I made the changes and reran the tests and nothing changed.

>
> 97:
>         // clause 4 - otherwise use unsigned version of the signed type
>             std::uintmax_t
> It isn't clear to me why uintmax_t is preferable
> to intmax_t when neither is able to represent every
> possible result.

If both operands are signed - then uintmax_t could hold
one more bit than uintmax_t can.  In these cases the
operand result can be twice as large before runtime
checking is necessary.

> 124:
>         using t_base_type = typename base_type<T>::type;
> This is called from safe_base_operations:259, which
> has already called base_type.
>
>   From the documentation, I had assumed that automatic
> used the range from safe_base.  However this range
> is not actually passed to the PromotionPolicy, so
> automatic always bumps the type to the next largest
> integer type, until it reaches [u]intmax_t.  This
> means than any expressions with more than a few
> terms will always be carried out using [u]intmax_t,
> which is potentially inefficient, e.g. intmax_t may
> require software implementation if it's larger
> than the hardware register size.

Clearly this is a sticky point.  There are two issues
here.  One is the result base type and the other is the
min/max range of safe result type returned. The return
safe type includes the proper range but may have
a base type which is larger than necessary.  I'll have
to look into this.

  A greater
> problem arises from the fact that mixed signed/unsigned
> arithmetic eventually chooses unsigned when the
> range is too large.  If we have a slightly complex
> expression with both signed and unsigned terms, the
> result type will eventually be selected as uintmax_t,
> which may be incapable of representing the result,
> thus causing an error.

Hmmm - My thinking for "automatic" was that it should mimic
the "native" C/C++ promotion but return a larger size. I'll
have to think about this some more.

  (I know that this scenario
> can also fail with builtin integer types, but
> it seems to me that the whole point of 'automatic'
> is to make things "just work" without having to
> worry about pesky things like signedness)

Right.  To the extent possible.

Looking at this obvervation, I see that native promotion
has the same problem in that it's unclear whether it
should take safe types or native base types as arguments.
More stuff to think about.

I'm sure that when I started out, I thought I had it
all clear in my mind.  But then as I worked through
my tests and examples, my "fixed" clouded the issue.

>
> 247:
>         using result_base_type = typename boost::mpl::if_c<
>             std::numeric_limits<t_base_type>::is_signed
>             || std::numeric_limits<u_base_type>::is_signed,
>             std::intmax_t,
>             std::uintmax_t
>         >::type;
> Why division doesn't use calculate_max_t like multiplication
> deserves some explanation.  Division can overflow
> too (numeric_limits<uintmax_t>::max() / 1).

Hmmm - I'm sure it's because I've presumed that the result
can aways be contained in the same size type as the number
being divide.  That t / x <= t - and divide by zero is
checked separately. Am I wrong about this?

>
> 275:
>     static constexpr divide(
> This function appears to be necessary, but is
> not documented as part of the PromotionPolicy
> concept.  The same goes for modulus.

Damn - I forgot about this. It couples the operation
with the promotion policy.  I spent an incredible
amount of time trying to avoid doing this.  But in the
end I just figure out how to do it.  So I had to put
these in.

>
> 328:
>     template<typename T, typename U>
>     struct left_shift_result
> Inconsistent with the documantation of PromotionPolicy
> which says: PP::left_shift_result<T>::type.  Same
> for right_shift_result, and bitwise_result.

Right

>
> 362:
>         using type = typename boost::mpl::if_c<
>             (sizeof(t_base_type) > sizeof(u_base_type)),
>             t_base_type,
>             u_base_type
>         >::type;
> Is it actually correct to combine &, |, and ^
> in the same class?  The result of & will always
> fit in the smaller type, but | and ^ require
> the larger type.

Right - I'll fix this

>
> checked.hpp:
>
> 90:
>             // INT32-C Ensure that operations on signed
>             // integers do not overflow
> This is the unsigned case.
>
> 220:
>   template<class R, class T, class U>
>   constexpr checked_result<R> add(
> Consider the following (assuming 2's complement):
> checked::add<int>(INT_MIN, UINT_MAX)
> The result should be INT_MAX,

I'm not seeing this.  With 8 bit ints we've got
INT_MIN = x80 = -128
UINT_MAX = x80 = 128
adding together x100
truncating = 0

which might be OK except on current machines but does violate the
standard in that it undefined behavior.  Given that compiler optimizers
can do anything they wand on UB I don't think we can do this

but your implementation
> will generate an error when converting UINT_MAX
> to int.

As I believe it should -

UINT_MAX = 0x80
convert to int - nothing changes
x80 interpreted as an int is -128

So this would transform an arithmetic value of 128 to
a value of -128.  Not a good thing.

What I've done is applied the standard. Convert each
type to the result type then do the addition.  On this
conversion we change the value - game over - invoke
error.

> 227:
>     if(! rt.no_exception() )
> The double negative makes this confusing to read.

Easy fix

>
> 230:
>     return detail::add<R>(t, u);
> This relies on implicit conversion and may generate
> spurious warnings.

conversion - I don't see it.  detail::add<R>(t, u)
return a checked_result<R> which is returned as another
checked_result<R>.  No conversion.  Probably not even
a copy with copy elusion.
>
> 301:
> Everything I said about add also applies to subtract.

OK - if we can agree on add we'll agree on subtract.
>
> 411:
>                     exception_type::underflow_error,
> This should be overflow_error.
OK
>
> 467:
> Again as with add.  This time the problematic case is
> multiply<unsigned>(-1, -1)

again - same response

>
> 539:
>     return detail::divide<R>(tx.m_r, ux.m_r);
> Just because m_r is public, doesn't mean that
> you should access it directly.

OK
>
> 583:
>   constexpr divide_automatic(
> The difference between divide and divide_automatic
> could use some explanation.  It looks like the only
> difference is that divide_automatic doesn't cast
> the divisor, but it isn't clear why.  Also, why
> do you need two checked divide functions in the
> first place?  There should really just be one
> that always works correctly.

LOL - that's what I thought. I couldn't make one which worked
for both native and automatic promotions.

The case which is giving me fits is dividing INT_MIN / -1

INT_MIN = 0x80 = -128
-128 / -1 = + 128 = 0x80 = INT_MIN again.

So we have INT_MIN / -1 -> INT_MIN an incorrect result.

Now I forget - but this is only a problem with automatic
promotions.

>
> 622:
>     return cast<R>(abs(t) % abs(u));
> This likely differs from the builtin % and should be documented
> as such.

Hmmm - slightly sticky issue here.  I used from &5.6/4

If both operands are nonnegative then the remainder is nonnegative; if 
not, the sign of the remainder is implementation-defined.

from ISO14882:2003(e) is no longer present in ISO14882:2011(e)

But even so my implementation should have trapped on negative
operands.

I'll consider what to do about this.

Also I prefer % to have the property that
> t / u * u + t % u = t, which this implementation
> does not satisfy.

I think this can be achieved

>
> 639:
>     // INT34-C C++ standard paragraph 5.8
>     if(u > std::numeric_limits<T>::digits){
> You're off-by-one
> "The behavior is undefined if the right operand
> is negative, or greater than *or equal to* the length in
> bits of the promoted left operand" (emphasis added)
>
> left_shift and right_shift (625-792) have several problems:
> - 640: You're checking the width of T even though the
>        actual shift is done after casting to R.
> - 696, 708: These overloads serve no purpose.  The
>        only difference between them is checks that
>        are already handled by check_shift.
> - 785: This test duplicates work done be check_shift

I've pretty much totally redid left and right shift last weekend.
I think they are more likely to be correct here.

>
> checked_result.hpp:
>
> 36:    // can't select constructor based on the current status of another
>
>     // checked_result object. So no copy constructor
> Saying that there is no copy constructor is misleading,
> as the default cctor exists and is used.
OK
>
> 67:
>         //assert(no_exception());
> Why is this commented out?  reading a
> not-currently-active member of a union
> is undefined behavior.

the assert conflicts with constexpr so I can't use it.
When one tries to cast to an R a compile time - it's trapped
just fine by my clang compiler on my mac.

The second case seems to pass because I never retrieve the
error message at compile time.

>
> 99:
>     constexpr boost::logic::tribool
>     operator<=(const checked_result<T> & t) const {
>         return ! operator>(t) && ! operator<(t);
>     }
> This is opertor==. The correct way is just ! operator>(t).
OK
>
> cpp.hpp:
>
> 54:
>     using rank =
> Rank is only used for comparisons.  I don't see
> any reason to use instead of using sizeof directly.
> This applies to automatic::rank as well.
> (Note: rank matters for builtin integer promotion,
> because types with the same size can have different
> ranks.  Your implementation of rank, however, is
> strictly based on size, making it essentially useless.)

Then I should probably change the implementation so
that types of different rank but the same size (e.g.
int and long on some machines) are handled correctly.
I don't think this is too hard to fix.
>
> exception.hpp:
>
> 15:
> // contains operations for doing checked aritmetic on NATIVE
>
> // C++ types.
> Wrong file.  Also s/aritmetic/arithmetic/ for
> wherever this was pasted from.
OK
>
> exception_policies.hpp:
>
> 1:
> #ifndef BOOST_NUMERIC_POLICIES_HPP
> #define BOOST_NUMERIC_POLICIES_HPP
> Make this BOOST_NUMERIC_EXCEPTION_POLICIES_HPP?
>
> interval.hpp:
>
> 18:
> #include <cstdlib> // quick_exit
> I don't see quick_exit anywhere in this file.
>
> 87:
> // account for the fact that for floats and doubles
> There's also long double, you know.
OK
>
> 101:
> namespace {
> Please don't use the unnamed namespace in headers.

OK - but I forgot why it's not recommended
>
> 133:
>
> template<typename R>
> constexpr bool less_than(
>     const checked_result<R> & lhs,
>     const checked_result<R> & rhs
> Why is this here and not in checked_result.hpp?

Removed

> Also this can be implemented easily using operator<:
>   return lhs < rhs;
> (The implicit conversion from tribool to bool
> does exactly what you want here.)

OK - I'll take your word for it.  used lhs < rhs in a lambda

>
> 257:
>             checked::modulus<R>(t.l, u.l),
>             checked::modulus<R>(t.l, u.u),
>             checked::modulus<R>(t.u, u.l),
>             checked::modulus<R>(t.u, u.u)
> This appears to be copied from divide, but it's totally
> wrong.  modulus is not monotonic, so you can't get
> away with checking only the boundaries.
>
> 339:
>     const R rl = safe_compare::greater_than(t.l, u.l) ? t.l : u.l;
> The implicit cast to R may not be safe.
> (same at 340, 356, and 357)

>
> 359:
>     if(safe_compare::greater_than(rl, ru)){
> This check isn't necessary.  The union of two non-empty
> intervals can't be empty.
OK
>
> 453:
> template<>
> std::ostream & operator<<(std::ostream & os, const
> boost::numeric::interval<unsigned char> & i)
> - This specialization is not a template, and can
>   only appear in one translation unit.
Please expand upon this

> - The implementation requires <ostream>, but you only #include <iosfwd>
Right = but any other which invokes this function will aready have
included ostream.  That's why included <iosfwd> rather than <ostream>
since this operator is used almost exclusively for debugging/examples.
>
> native.hpp:
>
> 27:
>     // Standard C++ type promotion for expressions doesn't depend
>     // on the operation being performed so we can just as well
>     // use any operation to determine it.  We choose + for this
>     // purpose.
> Comment out-dated.  The code (somewhat) uses decltype on the
> correct operators.
>
> safe_base.hpp:
>
> 240:
>     safe_base operator++(){      // pre increment
> pre-increment and pre-decrement should return by reference.
> post-increment and post-decrement should return by value.
> You currently have everything returning by value
> except post-decrement (which returns a dangling
> reference)
Right
>
> 258:
>     constexpr safe_base operator-() const { // unary minus
> should unary minus allow unsigned to become signed? (subject to
> the PromotionPolicy, of course).
LOL - I struggled with this - switched a couple of times back
and forth. I decided to leave the type the same.  That probably
conflicts with automatic promotion.  This still needs thinking
about.

>
> 261:
>     constexpr safe_base operator~() const {
> This will fail if Min/Max are anything other than
> the full range of the Stored type.
Right - but that's a common case.

>
> safe_base_operations.hpp:
>
> 82:
>         indeterminate(t_interval < this_interval),
> This works, but it would be a bit more intuitive
> if interval had an 'intersects' function.
H:mmmm it has intersection.  Would the following be better?

     static_assert(
         intersection<Stored>(t_interval, this_interval).exception(),
         "safe type cannot be constructed with this type"
     );

>
> 244:
> // Note: the following global operators will be only found via
> // argument dependent lookup.  So they won't conflict any
> // other global operators for types in namespaces other than
> // boost::numeric
> Unfortunately, ADL casts a very wide net.
> What makes these operators (mostly) safe
> is the use of enable_if.
>
> 267:
>     // Use base_value(T) ( which equals MIN ) to create a new interval. Same
>     // for MAX.  Now
> Now ... what?
>
> 288:
>     constexpr static const interval<result_base_type> type_interval =
>         exception_possible() ?
>             interval<result_base_type>{}
> This can overestimate the result interval if the
> interval only overflows on one side.

LOL - I never thought about that refinement.  I'll have to think about 
this. I'm thinking that this might well apply to most of the operations.

>
> 313:
>     using type_helper = typename boost::mpl::if_c<
>         std::numeric_limits<result_base_type>::is_integer,
>         safe_type,
>         unsafe_type
>     >::type;
> This is what?  Support for floating point in the future?

I think I put this in because of the possibility of
safe<int> x = 10;
float y = 10.0
auto z = x + y;

so z would be a float

Of course now I don't actually remember.  As I write this I don't feel
confident that I actually know what the above will do. Though I'm sure
I had an idea at one time.  I'll take another look.

>
> 531:
>         // when we add the temporary intervals above, we'll get a new
> interval
>         // with the correct range for the sum !
> I think you mean multiply and product, not add and sum.
>
of course
> 676:
>         constexpr static const interval<result_base_type> type_interval =
>             exception_possible() ?
> At this point, you lose any benefit of divide_nz over divide.
> You should check r_interval.exception() instead of exception_possible().
> The same goes for modulus.

Hmmm - still looking at this.

>
> 748:
>     // argument dependent lookup should guarentee that we only get here
> I don't understand this comment.
LOL - that makes two of us.
>
> 867:
>             static_cast<result_base_type>(base_value(t))
>
>             % static_cast<result_base_type>(base_value(u))
> Okay, we have a problem here: checked::modulus does /not/
> have the same behavior as the builtin % when the divisor
> is negative, which means that treating them as interchangable
> here will result in weird and inconsistent behavior (not to
> mention silently producing values outside the expected interval.)

I think fixing checked_modulus will address this
>
> 907:
> typename boost::lazy_enable_if_c<
>     ...,
>     boost::mpl::identity<bool>
> enable_if_c with bool should work just as well.
>
> 932:
>         // if the ranges don't overlap
>         (! boost::logic::indeterminate(r)) ?
>             // values in those ranges can't be equal
>             false
> This is operator<, not operator==.  You should return r, not false here.
> Same at 970 in operator>.  Also, you're already implementing
> operator<= and >= in terms of < and >.  Is there a reason
> to implement > separately?  (t > u) == (u < t)
>
> 1221:
>     // handle safe<T> << int, int << safe<U>, safe<T> << safe<U>
>     // exclude std::ostream << ...
> Copy/paste.  Should be >> and istream.
>
> 1276:
>
>             base_value(std::numeric_limits<T>::max())
> This doesn't take the input range into account and
> can drastically overestimate the result range.

I think I've fixed this.
>
> 1401:
>     using bwr = bitwise_or_result<T, U>;
> I think it would be slightly better to create an alias
> template<class T, class U>
> using bitwise_xor_result = bitwise_or_result<T, U>;
> instead of using bitwise_or_result directly in
> the implementation of xor.  (Note that the range
> of ^ can be larger than that of | if the lower bound
> of the parameters is greater than 0.)
>
> 1432, 1474:
>     class P, // promotion polic
> s/polic/policy/
>
> 1435:
> std::ostream & operator<<(
>     std::ostream & os,
> Should this use std::basic_ostream<CharT, Traits>?
I think so too.
>
> safe_common.hpp:
>
> safe_compare.hpp:
>
> safe_integer.hpp:
>
> safe_literal.hpp:
>
> 111:
>     constexpr safe_literal_impl operator-() const { // unary minus
> Err, what?  This will work iff. N is 0.
that's out
>
> 140:
> #define safe_literal(n)                               \
> This is not acceptable.  It totally violates
> the naming rules for macros.

I'm still struggling with this.  What do you suggest?
>
> safe_range.hpp:
>
> utility.hpp:
>
> 26:
>     constexpr log(T x){
> A function with a common name, that is not in a private
> namespace, and can match almost anything is a really
> bad idea.
Hmmm I could change this to something like bit_count
>
> concept/exception_policy.hpp:
>
> The reason that the check is commented out deserves
> explanation.  (Missing functions are acceptible and
> will cause a compile-time error instead of checking
> at runtime.)
>
> concept/*.hpp: no comments
>
> In Christ,
> Steven Watanabe
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>