[boost] Re: Formal Review Tribool

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2004-05-23 06:56:38

Le mer 19/05/2004 à 19:23, Thomas Witt a écrit :
> The review of Douglas Gregor's Tribool library begins now and runs
> through Saturday, May 29.

[...]

>      * What is your evaluation of the design?

There is not much to say. This library is small and implements a
well-known concept. It is restricted to 3-state boolean and not
extensible to bigger booleans but I don't think it is a flaw.

Operators ! && || have the expected semantic for tribool. It is not true
for == and != (the values could also be directly compared) but I don't
have a strong opinion on what the "good" semantic is. So the design is
good, except for this point imho:

Why is tribool default-initialized to false? Since tribool is supposed
to mimick bool, I would rather have no default value. Or if a default
value is necessary for practical use, indeterminate seems to me to be a
better choice than false.

>      * What is your evaluation of the implementation?

What is the purpose of safe_bool? I am asking the question because I was
unable to compile with GCC a code as simple as:
  tribool a; assert(a == a);
GCC complains that it "cannot convert `boost::logic::tribool' to `long
int' for argument `1' to `long int __builtin_expect(long int, long
int)'". It is obviously a problem caused by the definition of assert in
the library; but still... With a bool conversion operator, there is no
such problem.

The definitions of the comparison operators are not optimal and the
generated code is really bad. Something like this would be a lot more
efficient (at least with GCC but there is no reason the other compilers
would not benefit from this):

inline tribool operator==(tribool x, tribool y)
{
  if (indeterminate(x) || indeterminate(y))
    return indeterminate;
  else
    // return x && y || !x && !y;
    return x.value == y.value;
}

This code is 8 asm instructions long. The one in the tribool library
(the commented line) produces more than 70 asm instructions. The same is
true for !=.

The operators ! && || == != could also benefit from some bit-fiddling.
For example, the ! operator could be rewritten as "x.value ^ 1 ^
(x.value >> 1)" in order to suppress all conditional instructions.
However, contrarily to the previous rewriting, this one may hinder some
compilers during the conditional branch reduction step. It all depends
on the compiler and if the computed value is supposed to be stored
(bit-fiddling is good) or tested (bad). So let's just forget about this
idea.

tribool_io.hpp refers to <boost/utility/noncopyable.hpp> but this header
is not here. tribool_io_test.cpp should include <cassert>.

>      * What is your evaluation of the documentation?

The filenames are ugly but I suppose it is the fault of the automatic
documentation generator. The relative links to the headers and tests are
wrong. Other than these technical issues, I think the documentation is
good.

Concerning the tutorial, it should be mentioned the || and && operators
are not short-circuiting operators contrarily to the boolean versions. I
think it is important because it is a limitation of the implementation /
language, not an inherent property of tribool.

There is a problem with this example:
  assert(!(y == y)); // okay, because y == y is indeterminate
Since y == y is indeterminate, !(y == y) is too, and consequently assert
should not be okay, should it?

And just before, there is this comment:
  // neither x nor y is false, but we don't know that both are true
Shouldn't it be "neither x nor y is false and we know they are not both
true"? The next comment also need to be modified.

>      * What is your evaluation of the potential usefulness
>        of the library?

Such a type is really useful when manipulating objects that are not
totally ordered. Indeed the result of "a < b" can be neither true nor
false when the ordering is partial. The interval library would benefit
from such a facility for example.

>      * Did you try to use the library?  With what compiler?
>        Did you have any problems?

I did convert my old programs that were using tribool to this new
version. Except for the namespace change (from boost to boost::logic)
and the assert(tribool) issue, I had no problem. I only tested with GCC
3.[345] for the time being.

Please note that none of the logic/test files compiles with GCC. When a
conversion to bool is added, there is no more problem (yes, it is still
the assert(tribool) issue).

>      * How much effort did you put into your evaluation?
>        A glance? A quick reading? In-depth study?

Only a quick reading through the documentation since I have been a user
of the sandbox version (a bit modified) for a long time. I did not
review the I/O however; I prefer to let people more aware about
serialization issues do it.

>      * Are you knowledgeable about the problem domain?

Yes, as a user of this concept I know a bit about it. I also am a user
of the 9-state boolean defined by the IEEE 1164 standard.

>      * Do you think the library should be accepted as a Boost library?
>        Be sure to say this explicitly so that your other comments
>        don't obscure your overall opinion.

Yes.

Best regards,

Guillaume