| Message ID | 20170703122505.32017-3-mreitz@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On 07/03/2017 07:25 AM, Max Reitz wrote: > This generic function (along with its implementations for different > types) determines whether two QObjects are equal. > > Signed-off-by: Max Reitz <mreitz@redhat.com> > --- > +++ b/qobject/qnum.c > + case QNUM_DOUBLE: > + switch (num_y->kind) { > + case QNUM_I64: > + return qnum_is_equal(y, x); > + case QNUM_U64: > + return qnum_is_equal(y, x); > + case QNUM_DOUBLE: > + /* Comparison in native double type */ > + return num_x->u.dbl == num_y->u.dbl; Which returns false if we allow NaN (in general, JSON does not, so I'm not sure if we allow NaN in a QNum) > +++ b/qobject/qobject.c > +bool qobject_is_equal(const QObject *x, const QObject *y) > +{ > + /* We cannot test x == y because an object does not need to be > + * equal to itself (e.g. NaN floats are not). */ But this comment matches the code above in QNum. > + > + if (!x && !y) { > + return true; > + } > + > + if (!x || !y || x->type != y->type) { > + return false; > + } I like that there is no implicit conversion between bool and int; the only conversions that still allow equality are within the subtypes of QNum. Reviewed-by: Eric Blake <eblake@redhat.com>
Max Reitz <mreitz@redhat.com> writes: > This generic function (along with its implementations for different > types) determines whether two QObjects are equal. > > Signed-off-by: Max Reitz <mreitz@redhat.com> [...] > diff --git a/qobject/qnum.c b/qobject/qnum.c > index 476e81c..784d061 100644 > --- a/qobject/qnum.c > +++ b/qobject/qnum.c > @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) > } > > /** > + * qnum_is_equal(): Test whether the two QNums are equal > + */ > +bool qnum_is_equal(const QObject *x, const QObject *y) > +{ > + QNum *num_x = qobject_to_qnum(x); > + QNum *num_y = qobject_to_qnum(y); > + > + switch (num_x->kind) { > + case QNUM_I64: > + switch (num_y->kind) { > + case QNUM_I64: > + /* Comparison in native int64_t type */ > + return num_x->u.i64 == num_y->u.i64; > + case QNUM_U64: > + /* Implicit conversion of x to uin64_t, so we have to > + * check its sign before */ > + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; > + case QNUM_DOUBLE: > + /* Implicit conversion of x to double; no overflow > + * possible */ > + return num_x->u.i64 == num_y->u.dbl; Overflow is impossible, but loss of precision is possible: (double)9007199254740993ull == 9007199254740992.0 yields true. Is this what we want? > + } > + abort(); > + case QNUM_U64: > + switch (num_y->kind) { > + case QNUM_I64: > + return qnum_is_equal(y, x); > + case QNUM_U64: > + /* Comparison in native uint64_t type */ > + return num_x->u.u64 == num_y->u.u64; > + case QNUM_DOUBLE: > + /* Implicit conversion of x to double; no overflow > + * possible */ > + return num_x->u.u64 == num_y->u.dbl; Similar loss of precision. > + } > + abort(); > + case QNUM_DOUBLE: > + switch (num_y->kind) { > + case QNUM_I64: > + return qnum_is_equal(y, x); > + case QNUM_U64: > + return qnum_is_equal(y, x); > + case QNUM_DOUBLE: > + /* Comparison in native double type */ > + return num_x->u.dbl == num_y->u.dbl; > + } > + abort(); > + } > + > + abort(); > +} I think there's more than one sane interpretations of "is equal", including: * The mathematical numbers represented by @x and @y are equal. * @x and @y have the same contents, i.e. same kind and u. * @x and @y are the same object (listed for completeness; we don't need a function to compare pointers). Your patch implements yet another one. Which one do we want, and why? The second is easier to implement than the first. If we really want the first, you need to fix the loss of precision bugs. I guess the obvious fix is return (double)x == x && x == y; Note that this is what you do for mixed signedness: first check @x is exactly representable in @y's type, then compare in @y's type. Regardless of which one we pick, the function comment needs to explain. > + > +/** > * qnum_destroy_obj(): Free all memory allocated by a > * QNum object > */ [...] Remainder of the patch looks good to me.
On 2017-07-05 09:07, Markus Armbruster wrote: > Max Reitz <mreitz@redhat.com> writes: > >> This generic function (along with its implementations for different >> types) determines whether two QObjects are equal. >> >> Signed-off-by: Max Reitz <mreitz@redhat.com> > [...] >> diff --git a/qobject/qnum.c b/qobject/qnum.c >> index 476e81c..784d061 100644 >> --- a/qobject/qnum.c >> +++ b/qobject/qnum.c >> @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) >> } >> >> /** >> + * qnum_is_equal(): Test whether the two QNums are equal >> + */ >> +bool qnum_is_equal(const QObject *x, const QObject *y) >> +{ >> + QNum *num_x = qobject_to_qnum(x); >> + QNum *num_y = qobject_to_qnum(y); >> + >> + switch (num_x->kind) { >> + case QNUM_I64: >> + switch (num_y->kind) { >> + case QNUM_I64: >> + /* Comparison in native int64_t type */ >> + return num_x->u.i64 == num_y->u.i64; >> + case QNUM_U64: >> + /* Implicit conversion of x to uin64_t, so we have to >> + * check its sign before */ >> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >> + case QNUM_DOUBLE: >> + /* Implicit conversion of x to double; no overflow >> + * possible */ >> + return num_x->u.i64 == num_y->u.dbl; > > Overflow is impossible, but loss of precision is possible: > > (double)9007199254740993ull == 9007199254740992.0 > > yields true. Is this what we want? I'd argue that yes, because the floating point value represents basically all of the values which are "equal" to it. But I don't have a string opinion. I guess the alternative would be to convert the double to an integer instead and check for overflows before? >> + } >> + abort(); >> + case QNUM_U64: >> + switch (num_y->kind) { >> + case QNUM_I64: >> + return qnum_is_equal(y, x); >> + case QNUM_U64: >> + /* Comparison in native uint64_t type */ >> + return num_x->u.u64 == num_y->u.u64; >> + case QNUM_DOUBLE: >> + /* Implicit conversion of x to double; no overflow >> + * possible */ >> + return num_x->u.u64 == num_y->u.dbl; > > Similar loss of precision. > >> + } >> + abort(); >> + case QNUM_DOUBLE: >> + switch (num_y->kind) { >> + case QNUM_I64: >> + return qnum_is_equal(y, x); >> + case QNUM_U64: >> + return qnum_is_equal(y, x); >> + case QNUM_DOUBLE: >> + /* Comparison in native double type */ >> + return num_x->u.dbl == num_y->u.dbl; >> + } >> + abort(); >> + } >> + >> + abort(); >> +} > > I think there's more than one sane interpretations of "is equal", > including: > > * The mathematical numbers represented by @x and @y are equal. > > * @x and @y have the same contents, i.e. same kind and u. > > * @x and @y are the same object (listed for completeness; we don't need > a function to compare pointers). > > Your patch implements yet another one. Which one do we want, and why? Mine is the first one, except that I think that a floating point value does not represent a single number but just some number in a range. > The second is easier to implement than the first. It seems much less useful, though. > If we really want the first, you need to fix the loss of precision bugs. I'm not sure, but I don't mind either, so... > I guess the obvious fix is > > return (double)x == x && x == y; Yes, that would do, too; and spares me of having to think about how well comparing an arbitrary double to UINT64_MAX actually works. :-) > Note that this is what you do for mixed signedness: first check @x is > exactly representable in @y's type, then compare in @y's type. > > Regardless of which one we pick, the function comment needs to explain. OK, will do. Max >> + >> +/** >> * qnum_destroy_obj(): Free all memory allocated by a >> * QNum object >> */ > [...] > > Remainder of the patch looks good to me. >
On 07/05/2017 08:48 AM, Max Reitz wrote: >>> /** >>> + * qnum_is_equal(): Test whether the two QNums are equal >>> + */ >>> +bool qnum_is_equal(const QObject *x, const QObject *y) >>> +{ >>> + QNum *num_x = qobject_to_qnum(x); >>> + QNum *num_y = qobject_to_qnum(y); >>> + >>> + switch (num_x->kind) { >>> + case QNUM_I64: >>> + switch (num_y->kind) { >>> + case QNUM_I64: >>> + /* Comparison in native int64_t type */ >>> + return num_x->u.i64 == num_y->u.i64; >>> + case QNUM_U64: >>> + /* Implicit conversion of x to uin64_t, so we have to >>> + * check its sign before */ >>> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >>> + case QNUM_DOUBLE: >>> + /* Implicit conversion of x to double; no overflow >>> + * possible */ >>> + return num_x->u.i64 == num_y->u.dbl; >> >> Overflow is impossible, but loss of precision is possible: >> >> (double)9007199254740993ull == 9007199254740992.0 >> >> yields true. Is this what we want? > > I'd argue that yes, because the floating point value represents > basically all of the values which are "equal" to it. But the problem is that we CAN represent the fully-precise number as an integer, so having multiple distinct integers that compare differently against each other, but equal to the same double, is awkward. > > But I don't have a string opinion. I guess the alternative would be to > convert the double to an integer instead and check for overflows before? That's the solution Markus gave, and I'm in favor of the tighter check: > >> I guess the obvious fix is >> >> return (double)x == x && x == y; > > Yes, that would do, too; and spares me of having to think about how well > comparing an arbitrary double to UINT64_MAX actually works. :-) It basically says that we are unwilling to declare an integer equivalent to the double if the double loses precision when trying to store the integer.
On 2017-07-05 15:48, Max Reitz wrote: > On 2017-07-05 09:07, Markus Armbruster wrote: >> Max Reitz <mreitz@redhat.com> writes: >> >>> This generic function (along with its implementations for different >>> types) determines whether two QObjects are equal. >>> >>> Signed-off-by: Max Reitz <mreitz@redhat.com> >> [...] >>> diff --git a/qobject/qnum.c b/qobject/qnum.c >>> index 476e81c..784d061 100644 >>> --- a/qobject/qnum.c >>> +++ b/qobject/qnum.c >>> @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) >>> } >>> >>> /** >>> + * qnum_is_equal(): Test whether the two QNums are equal >>> + */ >>> +bool qnum_is_equal(const QObject *x, const QObject *y) >>> +{ >>> + QNum *num_x = qobject_to_qnum(x); >>> + QNum *num_y = qobject_to_qnum(y); >>> + >>> + switch (num_x->kind) { >>> + case QNUM_I64: >>> + switch (num_y->kind) { >>> + case QNUM_I64: >>> + /* Comparison in native int64_t type */ >>> + return num_x->u.i64 == num_y->u.i64; >>> + case QNUM_U64: >>> + /* Implicit conversion of x to uin64_t, so we have to >>> + * check its sign before */ >>> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >>> + case QNUM_DOUBLE: >>> + /* Implicit conversion of x to double; no overflow >>> + * possible */ >>> + return num_x->u.i64 == num_y->u.dbl; >> >> Overflow is impossible, but loss of precision is possible: >> >> (double)9007199254740993ull == 9007199254740992.0 >> >> yields true. Is this what we want? > > I'd argue that yes, because the floating point value represents > basically all of the values which are "equal" to it. > > But I don't have a string opinion. I guess the alternative would be to > convert the double to an integer instead and check for overflows before? > >>> + } >>> + abort(); >>> + case QNUM_U64: >>> + switch (num_y->kind) { >>> + case QNUM_I64: >>> + return qnum_is_equal(y, x); >>> + case QNUM_U64: >>> + /* Comparison in native uint64_t type */ >>> + return num_x->u.u64 == num_y->u.u64; >>> + case QNUM_DOUBLE: >>> + /* Implicit conversion of x to double; no overflow >>> + * possible */ >>> + return num_x->u.u64 == num_y->u.dbl; >> >> Similar loss of precision. >> >>> + } >>> + abort(); >>> + case QNUM_DOUBLE: >>> + switch (num_y->kind) { >>> + case QNUM_I64: >>> + return qnum_is_equal(y, x); >>> + case QNUM_U64: >>> + return qnum_is_equal(y, x); >>> + case QNUM_DOUBLE: >>> + /* Comparison in native double type */ >>> + return num_x->u.dbl == num_y->u.dbl; >>> + } >>> + abort(); >>> + } >>> + >>> + abort(); >>> +} >> >> I think there's more than one sane interpretations of "is equal", >> including: >> >> * The mathematical numbers represented by @x and @y are equal. >> >> * @x and @y have the same contents, i.e. same kind and u. >> >> * @x and @y are the same object (listed for completeness; we don't need >> a function to compare pointers). >> >> Your patch implements yet another one. Which one do we want, and why? > > Mine is the first one, except that I think that a floating point value > does not represent a single number but just some number in a range. > >> The second is easier to implement than the first. > > It seems much less useful, though. > >> If we really want the first, you need to fix the loss of precision bugs. > > I'm not sure, but I don't mind either, so... > >> I guess the obvious fix is >> >> return (double)x == x && x == y; > > Yes, that would do, too; and spares me of having to think about how well > comparing an arbitrary double to UINT64_MAX actually works. :-) On second thought, this won't do, because (double)x == x is always true if x is an integer (because this will implicitly cast the second x to a double, too). However, (uint64_t)(double)x == x should work. Max > >> Note that this is what you do for mixed signedness: first check @x is >> exactly representable in @y's type, then compare in @y's type. >> >> Regardless of which one we pick, the function comment needs to explain. > > OK, will do. > > Max > >>> + >>> +/** >>> * qnum_destroy_obj(): Free all memory allocated by a >>> * QNum object >>> */ >> [...] >> >> Remainder of the patch looks good to me. >> > >
Eric Blake <eblake@redhat.com> writes: > On 07/05/2017 08:48 AM, Max Reitz wrote: >>>> /** >>>> + * qnum_is_equal(): Test whether the two QNums are equal >>>> + */ >>>> +bool qnum_is_equal(const QObject *x, const QObject *y) >>>> +{ >>>> + QNum *num_x = qobject_to_qnum(x); >>>> + QNum *num_y = qobject_to_qnum(y); >>>> + >>>> + switch (num_x->kind) { >>>> + case QNUM_I64: >>>> + switch (num_y->kind) { >>>> + case QNUM_I64: >>>> + /* Comparison in native int64_t type */ >>>> + return num_x->u.i64 == num_y->u.i64; >>>> + case QNUM_U64: >>>> + /* Implicit conversion of x to uin64_t, so we have to >>>> + * check its sign before */ >>>> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >>>> + case QNUM_DOUBLE: >>>> + /* Implicit conversion of x to double; no overflow >>>> + * possible */ >>>> + return num_x->u.i64 == num_y->u.dbl; >>> >>> Overflow is impossible, but loss of precision is possible: >>> >>> (double)9007199254740993ull == 9007199254740992.0 >>> >>> yields true. Is this what we want? >> >> I'd argue that yes, because the floating point value represents >> basically all of the values which are "equal" to it. > > But the problem is that we CAN represent the fully-precise number as an > integer, so having multiple distinct integers that compare differently > against each other, but equal to the same double, is awkward. Yup. >> But I don't have a string opinion. I guess the alternative would be to >> convert the double to an integer instead and check for overflows before? > > That's the solution Markus gave, and I'm in favor of the tighter check: > [...] >>> I think there's more than one sane interpretations of "is equal", >>> including: >>> >>> * The mathematical numbers represented by @x and @y are equal. >>> >>> * @x and @y have the same contents, i.e. same kind and u. >>> >>> * @x and @y are the same object (listed for completeness; we don't need >>> a function to compare pointers). >>> >>> Your patch implements yet another one. Which one do we want, and why? >> >> Mine is the first one, except that I think that a floating point value >> does not represent a single number but just some number in a range. >> >>> The second is easier to implement than the first. >> >> It seems much less useful, though. Depends on what for. Common Lisp has * eq: same object * eql: eq, or both numbers with same type and value, or both characters that represent the same character * =: mathematically equal (arguments must be numbers) * equal: like eql, but it recursively descends into lists (I'm simplifying) Decades of use back the assertion that eq, eql and = are all useful. >>> If we really want the first, you need to fix the loss of precision bugs. >> >> I'm not sure, but I don't mind either, so... For what it's worth, your v2 had QInt compare not equal to QFloat. Makes me suspect that eql is good enough for the problem at hand. >>> I guess the obvious fix is >>> >>> return (double)x == x && x == y; >> >> Yes, that would do, too; and spares me of having to think about how well >> comparing an arbitrary double to UINT64_MAX actually works. :-) > > It basically says that we are unwilling to declare an integer equivalent > to the double if the double loses precision when trying to store the > integer. > >>> Note that this is what you do for mixed signedness: first check @x is >>> exactly representable in @y's type, then compare in @y's type. >>> >>> Regardless of which one we pick, the function comment needs to explain.
On 2017-07-05 18:05, Max Reitz wrote: > On 2017-07-05 15:48, Max Reitz wrote: >> On 2017-07-05 09:07, Markus Armbruster wrote: >>> Max Reitz <mreitz@redhat.com> writes: >>> >>>> This generic function (along with its implementations for different >>>> types) determines whether two QObjects are equal. >>>> >>>> Signed-off-by: Max Reitz <mreitz@redhat.com> >>> [...] >>>> diff --git a/qobject/qnum.c b/qobject/qnum.c >>>> index 476e81c..784d061 100644 >>>> --- a/qobject/qnum.c >>>> +++ b/qobject/qnum.c >>>> @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) >>>> } >>>> >>>> /** >>>> + * qnum_is_equal(): Test whether the two QNums are equal >>>> + */ >>>> +bool qnum_is_equal(const QObject *x, const QObject *y) >>>> +{ >>>> + QNum *num_x = qobject_to_qnum(x); >>>> + QNum *num_y = qobject_to_qnum(y); >>>> + >>>> + switch (num_x->kind) { >>>> + case QNUM_I64: >>>> + switch (num_y->kind) { >>>> + case QNUM_I64: >>>> + /* Comparison in native int64_t type */ >>>> + return num_x->u.i64 == num_y->u.i64; >>>> + case QNUM_U64: >>>> + /* Implicit conversion of x to uin64_t, so we have to >>>> + * check its sign before */ >>>> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >>>> + case QNUM_DOUBLE: >>>> + /* Implicit conversion of x to double; no overflow >>>> + * possible */ >>>> + return num_x->u.i64 == num_y->u.dbl; >>> >>> Overflow is impossible, but loss of precision is possible: >>> >>> (double)9007199254740993ull == 9007199254740992.0 >>> >>> yields true. Is this what we want? >> >> I'd argue that yes, because the floating point value represents >> basically all of the values which are "equal" to it. >> >> But I don't have a string opinion. I guess the alternative would be to >> convert the double to an integer instead and check for overflows before? >> >>>> + } >>>> + abort(); >>>> + case QNUM_U64: >>>> + switch (num_y->kind) { >>>> + case QNUM_I64: >>>> + return qnum_is_equal(y, x); >>>> + case QNUM_U64: >>>> + /* Comparison in native uint64_t type */ >>>> + return num_x->u.u64 == num_y->u.u64; >>>> + case QNUM_DOUBLE: >>>> + /* Implicit conversion of x to double; no overflow >>>> + * possible */ >>>> + return num_x->u.u64 == num_y->u.dbl; >>> >>> Similar loss of precision. >>> >>>> + } >>>> + abort(); >>>> + case QNUM_DOUBLE: >>>> + switch (num_y->kind) { >>>> + case QNUM_I64: >>>> + return qnum_is_equal(y, x); >>>> + case QNUM_U64: >>>> + return qnum_is_equal(y, x); >>>> + case QNUM_DOUBLE: >>>> + /* Comparison in native double type */ >>>> + return num_x->u.dbl == num_y->u.dbl; >>>> + } >>>> + abort(); >>>> + } >>>> + >>>> + abort(); >>>> +} >>> >>> I think there's more than one sane interpretations of "is equal", >>> including: >>> >>> * The mathematical numbers represented by @x and @y are equal. >>> >>> * @x and @y have the same contents, i.e. same kind and u. >>> >>> * @x and @y are the same object (listed for completeness; we don't need >>> a function to compare pointers). >>> >>> Your patch implements yet another one. Which one do we want, and why? >> >> Mine is the first one, except that I think that a floating point value >> does not represent a single number but just some number in a range. >> >>> The second is easier to implement than the first. >> >> It seems much less useful, though. >> >>> If we really want the first, you need to fix the loss of precision bugs. >> >> I'm not sure, but I don't mind either, so... >> >>> I guess the obvious fix is >>> >>> return (double)x == x && x == y; >> >> Yes, that would do, too; and spares me of having to think about how well >> comparing an arbitrary double to UINT64_MAX actually works. :-) > > On second thought, this won't do, because (double)x == x is always true > if x is an integer (because this will implicitly cast the second x to a > double, too). However, (uint64_t)(double)x == x should work. Hm, well, the nice thing with this is that (double)UINT64_MAX is actually UINT64_MAX + 1, and now (uint64_t)(UINT64_MAX + 1) is undefined... Urgs. So I guess one thing that isn't very obvious but that should *always* work (and is always well-defined) is this: For uint64_t: y < 0x1p64 && (uint64_t)y == x For int64_t: y >= -0x1p63 && y < 0x1p63 && (int64_t)y == x I hope. :-/ (But finally a chance to use binary exponents! Yay!) Max
On 07/05/2017 11:22 AM, Max Reitz wrote: >>>> return (double)x == x && x == y; >>> >>> Yes, that would do, too; and spares me of having to think about how well >>> comparing an arbitrary double to UINT64_MAX actually works. :-) >> >> On second thought, this won't do, because (double)x == x is always true >> if x is an integer (because this will implicitly cast the second x to a >> double, too). However, (uint64_t)(double)x == x should work. > > Hm, well, the nice thing with this is that (double)UINT64_MAX is > actually UINT64_MAX + 1, and now (uint64_t)(UINT64_MAX + 1) is > undefined... Urgs. (uint64_t)(UINT64_MAX + 1) is well-defined - it is 0. (Adding in unsigned integers is always well-defined - it wraps around on mathematical overflow modulo the integer size. You're thinking of overflow addition on signed integers, which is indeed undefined) > > So I guess one thing that isn't very obvious but that should *always* > work (and is always well-defined) is this: > > For uint64_t: y < 0x1p64 && (uint64_t)y == x > > For int64_t: y >= -0x1p63 && y < 0x1p63 && (int64_t)y == x That's harder to read, compared to the double-cast method which is well-defined after all. > > I hope. :-/ > > (But finally a chance to use binary exponents! Yay!) Justifying the use of binary exponents is going to be harder than that, and would need a really good comment in the code, compared to just using a safe double-cast.
On 2017-07-05 18:22, Max Reitz wrote: > On 2017-07-05 18:05, Max Reitz wrote: >> On 2017-07-05 15:48, Max Reitz wrote: >>> On 2017-07-05 09:07, Markus Armbruster wrote: >>>> Max Reitz <mreitz@redhat.com> writes: >>>> >>>>> This generic function (along with its implementations for different >>>>> types) determines whether two QObjects are equal. >>>>> >>>>> Signed-off-by: Max Reitz <mreitz@redhat.com> >>>> [...] >>>>> diff --git a/qobject/qnum.c b/qobject/qnum.c >>>>> index 476e81c..784d061 100644 >>>>> --- a/qobject/qnum.c >>>>> +++ b/qobject/qnum.c >>>>> @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) >>>>> } >>>>> >>>>> /** >>>>> + * qnum_is_equal(): Test whether the two QNums are equal >>>>> + */ >>>>> +bool qnum_is_equal(const QObject *x, const QObject *y) >>>>> +{ >>>>> + QNum *num_x = qobject_to_qnum(x); >>>>> + QNum *num_y = qobject_to_qnum(y); >>>>> + >>>>> + switch (num_x->kind) { >>>>> + case QNUM_I64: >>>>> + switch (num_y->kind) { >>>>> + case QNUM_I64: >>>>> + /* Comparison in native int64_t type */ >>>>> + return num_x->u.i64 == num_y->u.i64; >>>>> + case QNUM_U64: >>>>> + /* Implicit conversion of x to uin64_t, so we have to >>>>> + * check its sign before */ >>>>> + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; >>>>> + case QNUM_DOUBLE: >>>>> + /* Implicit conversion of x to double; no overflow >>>>> + * possible */ >>>>> + return num_x->u.i64 == num_y->u.dbl; >>>> >>>> Overflow is impossible, but loss of precision is possible: >>>> >>>> (double)9007199254740993ull == 9007199254740992.0 >>>> >>>> yields true. Is this what we want? >>> >>> I'd argue that yes, because the floating point value represents >>> basically all of the values which are "equal" to it. >>> >>> But I don't have a string opinion. I guess the alternative would be to >>> convert the double to an integer instead and check for overflows before? >>> >>>>> + } >>>>> + abort(); >>>>> + case QNUM_U64: >>>>> + switch (num_y->kind) { >>>>> + case QNUM_I64: >>>>> + return qnum_is_equal(y, x); >>>>> + case QNUM_U64: >>>>> + /* Comparison in native uint64_t type */ >>>>> + return num_x->u.u64 == num_y->u.u64; >>>>> + case QNUM_DOUBLE: >>>>> + /* Implicit conversion of x to double; no overflow >>>>> + * possible */ >>>>> + return num_x->u.u64 == num_y->u.dbl; >>>> >>>> Similar loss of precision. >>>> >>>>> + } >>>>> + abort(); >>>>> + case QNUM_DOUBLE: >>>>> + switch (num_y->kind) { >>>>> + case QNUM_I64: >>>>> + return qnum_is_equal(y, x); >>>>> + case QNUM_U64: >>>>> + return qnum_is_equal(y, x); >>>>> + case QNUM_DOUBLE: >>>>> + /* Comparison in native double type */ >>>>> + return num_x->u.dbl == num_y->u.dbl; >>>>> + } >>>>> + abort(); >>>>> + } >>>>> + >>>>> + abort(); >>>>> +} >>>> >>>> I think there's more than one sane interpretations of "is equal", >>>> including: >>>> >>>> * The mathematical numbers represented by @x and @y are equal. >>>> >>>> * @x and @y have the same contents, i.e. same kind and u. >>>> >>>> * @x and @y are the same object (listed for completeness; we don't need >>>> a function to compare pointers). >>>> >>>> Your patch implements yet another one. Which one do we want, and why? >>> >>> Mine is the first one, except that I think that a floating point value >>> does not represent a single number but just some number in a range. >>> >>>> The second is easier to implement than the first. >>> >>> It seems much less useful, though. >>> >>>> If we really want the first, you need to fix the loss of precision bugs. >>> >>> I'm not sure, but I don't mind either, so... >>> >>>> I guess the obvious fix is >>>> >>>> return (double)x == x && x == y; >>> >>> Yes, that would do, too; and spares me of having to think about how well >>> comparing an arbitrary double to UINT64_MAX actually works. :-) >> >> On second thought, this won't do, because (double)x == x is always true >> if x is an integer (because this will implicitly cast the second x to a >> double, too). However, (uint64_t)(double)x == x should work. > > Hm, well, the nice thing with this is that (double)UINT64_MAX is > actually UINT64_MAX + 1, and now (uint64_t)(UINT64_MAX + 1) is > undefined... Urgs. > > So I guess one thing that isn't very obvious but that should *always* > work (and is always well-defined) is this: > > For uint64_t: y < 0x1p64 && (uint64_t)y == x Here comes iteration number 4: Forgot the y >= 0 check. > For int64_t: y >= -0x1p63 && y < 0x1p63 && (int64_t)y == x Also, I should check that the fractional part of y is 0 (through modf(y, &_) == 0.0). Floating point numbers are so much fun! (And all of this gives me such great ideas for tests to add to patch 5!) Max > I hope. :-/ > > (But finally a chance to use binary exponents! Yay!) > > Max >
On 2017-07-05 18:29, Eric Blake wrote: > On 07/05/2017 11:22 AM, Max Reitz wrote: > >>>>> return (double)x == x && x == y; >>>> >>>> Yes, that would do, too; and spares me of having to think about how well >>>> comparing an arbitrary double to UINT64_MAX actually works. :-) >>> >>> On second thought, this won't do, because (double)x == x is always true >>> if x is an integer (because this will implicitly cast the second x to a >>> double, too). However, (uint64_t)(double)x == x should work. >> >> Hm, well, the nice thing with this is that (double)UINT64_MAX is >> actually UINT64_MAX + 1, and now (uint64_t)(UINT64_MAX + 1) is >> undefined... Urgs. > > (uint64_t)(UINT64_MAX + 1) is well-defined - it is 0. > > (Adding in unsigned integers is always well-defined - it wraps around on > mathematical overflow modulo the integer size. You're thinking of > overflow addition on signed integers, which is indeed undefined) It's not. See the standard: When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. [61] [61] The remaindering operation performed when a value of integer type is converted to unsigned type need not be performed when a value of real floating type is converted to unsigned type. Thus, the range of portable real floating values is (−1, Utype_MAX+1). See for yourself: printf("%i\n", (uint64_t)(double)UINT64_MAX == UINT64_MAX); This yields 1 with gcc and -O3. >> >> So I guess one thing that isn't very obvious but that should *always* >> work (and is always well-defined) is this: >> >> For uint64_t: y < 0x1p64 && (uint64_t)y == x >> >> For int64_t: y >= -0x1p63 && y < 0x1p63 && (int64_t)y == x > > That's harder to read, compared to the double-cast method which is > well-defined after all. > >> >> I hope. :-/ >> >> (But finally a chance to use binary exponents! Yay!) > > Justifying the use of binary exponents is going to be harder than that, > and would need a really good comment in the code, compared to just using > a safe double-cast. It's not safe. Max
On 2017-07-05 19:00, Max Reitz wrote: > On 2017-07-05 18:29, Eric Blake wrote: >> On 07/05/2017 11:22 AM, Max Reitz wrote: >> >>>>>> return (double)x == x && x == y; >>>>> >>>>> Yes, that would do, too; and spares me of having to think about how well >>>>> comparing an arbitrary double to UINT64_MAX actually works. :-) >>>> >>>> On second thought, this won't do, because (double)x == x is always true >>>> if x is an integer (because this will implicitly cast the second x to a >>>> double, too). However, (uint64_t)(double)x == x should work. >>> >>> Hm, well, the nice thing with this is that (double)UINT64_MAX is >>> actually UINT64_MAX + 1, and now (uint64_t)(UINT64_MAX + 1) is >>> undefined... Urgs. >> >> (uint64_t)(UINT64_MAX + 1) is well-defined - it is 0. >> >> (Adding in unsigned integers is always well-defined - it wraps around on >> mathematical overflow modulo the integer size. You're thinking of >> overflow addition on signed integers, which is indeed undefined) > > It's not. See the standard: Or, well, yes, it is in this case, but I meant literally UINT64_MAX + 1, not the uint64_t value. I meant the natural number 2^64. Because the issue is that (double)UINT64_MAX will (or may, depending on the environment and such) give us 2.0^64 == 0x1p64. And this is where the quotation I gave below comes in. When casting an integer to a double we may end up with a value that is not representable in the original integer type, so we cannot easily cast it back. Max > When a finite value of real floating type is converted to an integer > type other than _Bool, the fractional part is discarded (i.e., the value > is truncated toward zero). If the value of the integral part cannot be > represented by the integer type, the behavior is undefined. [61] > > [61] The remaindering operation performed when a value of integer type > is converted to unsigned type need not be performed when a value of real > floating type is converted to unsigned type. Thus, the range of portable > real floating values is (−1, Utype_MAX+1). > > See for yourself: > > printf("%i\n", (uint64_t)(double)UINT64_MAX == UINT64_MAX); > > This yields 1 with gcc and -O3. > >>> >>> So I guess one thing that isn't very obvious but that should *always* >>> work (and is always well-defined) is this: >>> >>> For uint64_t: y < 0x1p64 && (uint64_t)y == x >>> >>> For int64_t: y >= -0x1p63 && y < 0x1p63 && (int64_t)y == x >> >> That's harder to read, compared to the double-cast method which is >> well-defined after all. >> >>> >>> I hope. :-/ >>> >>> (But finally a chance to use binary exponents! Yay!) >> >> Justifying the use of binary exponents is going to be harder than that, >> and would need a really good comment in the code, compared to just using >> a safe double-cast. > > It's not safe. > > Max >
On 07/05/2017 12:00 PM, Max Reitz wrote: >> (uint64_t)(UINT64_MAX + 1) is well-defined - it is 0. >> >> (Adding in unsigned integers is always well-defined - it wraps around on >> mathematical overflow modulo the integer size. You're thinking of >> overflow addition on signed integers, which is indeed undefined) > > It's not. See the standard: > > When a finite value of real floating type is converted to an integer Ah, you're talking: (uint64_t)(double)(UINT64_MAX + 1), which is indeed undefined.
On 07/05/2017 12:04 PM, Max Reitz wrote: > Or, well, yes, it is in this case, but I meant literally UINT64_MAX + 1, > not the uint64_t value. I meant the natural number 2^64. > > Because the issue is that (double)UINT64_MAX will (or may, depending on > the environment and such) give us 2.0^64 == 0x1p64. > > And this is where the quotation I gave below comes in. When casting an > integer to a double we may end up with a value that is not representable > in the original integer type, so we cannot easily cast it back. And it's more than just UINT64_MAX that rounds to the double value of 0x1p64. Okay, I'm starting to be convinced that using a floating-point comparison to 0x1p64 is going to be easier than an integer comparison to the rounding point (what point is that, anyways: where the low-order 11 bits that don't fit in 53 bits of precision cause us to round up instead of down?) >>> Justifying the use of binary exponents is going to be harder than that, >>> and would need a really good comment in the code, compared to just using >>> a safe double-cast. >> >> It's not safe. >> >> Max >> > >
diff --git a/include/qapi/qmp/qbool.h b/include/qapi/qmp/qbool.h index a41111c..f77ea86 100644 --- a/include/qapi/qmp/qbool.h +++ b/include/qapi/qmp/qbool.h @@ -24,6 +24,7 @@ typedef struct QBool { QBool *qbool_from_bool(bool value); bool qbool_get_bool(const QBool *qb); QBool *qobject_to_qbool(const QObject *obj); +bool qbool_is_equal(const QObject *x, const QObject *y); void qbool_destroy_obj(QObject *obj); #endif /* QBOOL_H */ diff --git a/include/qapi/qmp/qdict.h b/include/qapi/qmp/qdict.h index 363e431..84f8ea7 100644 --- a/include/qapi/qmp/qdict.h +++ b/include/qapi/qmp/qdict.h @@ -42,6 +42,7 @@ void qdict_del(QDict *qdict, const char *key); int qdict_haskey(const QDict *qdict, const char *key); QObject *qdict_get(const QDict *qdict, const char *key); QDict *qobject_to_qdict(const QObject *obj); +bool qdict_is_equal(const QObject *x, const QObject *y); void qdict_iter(const QDict *qdict, void (*iter)(const char *key, QObject *obj, void *opaque), void *opaque); diff --git a/include/qapi/qmp/qlist.h b/include/qapi/qmp/qlist.h index c4b5fda..24e1e9f 100644 --- a/include/qapi/qmp/qlist.h +++ b/include/qapi/qmp/qlist.h @@ -58,6 +58,7 @@ QObject *qlist_peek(QList *qlist); int qlist_empty(const QList *qlist); size_t qlist_size(const QList *qlist); QList *qobject_to_qlist(const QObject *obj); +bool qlist_is_equal(const QObject *x, const QObject *y); void qlist_destroy_obj(QObject *obj); static inline const QListEntry *qlist_first(const QList *qlist) diff --git a/include/qapi/qmp/qnull.h b/include/qapi/qmp/qnull.h index 48edad4..f4fbcae 100644 --- a/include/qapi/qmp/qnull.h +++ b/include/qapi/qmp/qnull.h @@ -23,4 +23,6 @@ static inline QObject *qnull(void) return &qnull_; } +bool qnull_is_equal(const QObject *x, const QObject *y); + #endif /* QNULL_H */ diff --git a/include/qapi/qmp/qnum.h b/include/qapi/qmp/qnum.h index 09d745c..237d01b 100644 --- a/include/qapi/qmp/qnum.h +++ b/include/qapi/qmp/qnum.h @@ -48,6 +48,7 @@ double qnum_get_double(QNum *qn); char *qnum_to_string(QNum *qn); QNum *qobject_to_qnum(const QObject *obj); +bool qnum_is_equal(const QObject *x, const QObject *y); void qnum_destroy_obj(QObject *obj); #endif /* QNUM_H */ diff --git a/include/qapi/qmp/qobject.h b/include/qapi/qmp/qobject.h index ef1d1a9..38ac688 100644 --- a/include/qapi/qmp/qobject.h +++ b/include/qapi/qmp/qobject.h @@ -68,6 +68,15 @@ static inline void qobject_incref(QObject *obj) } /** + * qobject_is_equal(): Return whether the two objects are equal. + * + * Any of the pointers may be NULL; return true if both are. Always + * return false if only one is (therefore a QNull object is not + * considered equal to a NULL pointer). + */ +bool qobject_is_equal(const QObject *x, const QObject *y); + +/** * qobject_destroy(): Free resources used by the object */ void qobject_destroy(QObject *obj); diff --git a/include/qapi/qmp/qstring.h b/include/qapi/qmp/qstring.h index 10076b7..65c05a9 100644 --- a/include/qapi/qmp/qstring.h +++ b/include/qapi/qmp/qstring.h @@ -31,6 +31,7 @@ void qstring_append_int(QString *qstring, int64_t value); void qstring_append(QString *qstring, const char *str); void qstring_append_chr(QString *qstring, int c); QString *qobject_to_qstring(const QObject *obj); +bool qstring_is_equal(const QObject *x, const QObject *y); void qstring_destroy_obj(QObject *obj); #endif /* QSTRING_H */ diff --git a/qobject/qbool.c b/qobject/qbool.c index 0606bbd..ac825fc 100644 --- a/qobject/qbool.c +++ b/qobject/qbool.c @@ -52,6 +52,14 @@ QBool *qobject_to_qbool(const QObject *obj) } /** + * qbool_is_equal(): Test whether the two QBools are equal + */ +bool qbool_is_equal(const QObject *x, const QObject *y) +{ + return qobject_to_qbool(x)->value == qobject_to_qbool(y)->value; +} + +/** * qbool_destroy_obj(): Free all memory allocated by a * QBool object */ diff --git a/qobject/qdict.c b/qobject/qdict.c index 576018e..e8f15f1 100644 --- a/qobject/qdict.c +++ b/qobject/qdict.c @@ -403,6 +403,35 @@ void qdict_del(QDict *qdict, const char *key) } /** + * qdict_is_equal(): Test whether the two QDicts are equal + * + * Here, equality means whether they contain the same keys and whether + * the respective values are in turn equal (i.e. invoking + * qobject_is_equal() on them yields true). + */ +bool qdict_is_equal(const QObject *x, const QObject *y) +{ + const QDict *dict_x = qobject_to_qdict(x); + const QDict *dict_y = qobject_to_qdict(y); + const QDictEntry *e; + + if (qdict_size(dict_x) != qdict_size(dict_y)) { + return false; + } + + for (e = qdict_first(dict_x); e; e = qdict_next(dict_x, e)) { + const QObject *obj_x = qdict_entry_value(e); + const QObject *obj_y = qdict_get(dict_y, qdict_entry_key(e)); + + if (!qobject_is_equal(obj_x, obj_y)) { + return false; + } + } + + return true; +} + +/** * qdict_destroy_obj(): Free all the memory allocated by a QDict */ void qdict_destroy_obj(QObject *obj) diff --git a/qobject/qlist.c b/qobject/qlist.c index 86b60cb..3ef57d3 100644 --- a/qobject/qlist.c +++ b/qobject/qlist.c @@ -140,6 +140,38 @@ QList *qobject_to_qlist(const QObject *obj) } /** + * qlist_is_equal(): Test whether the two QLists are equal + * + * In order to be considered equal, the respective two objects at each + * index of the two lists have to compare equal (regarding + * qobject_is_equal()), and both lists have to have the same number of + * elements. + * That means both lists have to contain equal objects in equal order. + */ +bool qlist_is_equal(const QObject *x, const QObject *y) +{ + const QList *list_x = qobject_to_qlist(x); + const QList *list_y = qobject_to_qlist(y); + const QListEntry *entry_x, *entry_y; + + entry_x = qlist_first(list_x); + entry_y = qlist_first(list_y); + + while (entry_x && entry_y) { + if (!qobject_is_equal(qlist_entry_obj(entry_x), + qlist_entry_obj(entry_y))) + { + return false; + } + + entry_x = qlist_next(entry_x); + entry_y = qlist_next(entry_y); + } + + return !entry_x && !entry_y; +} + +/** * qlist_destroy_obj(): Free all the memory allocated by a QList */ void qlist_destroy_obj(QObject *obj) diff --git a/qobject/qnull.c b/qobject/qnull.c index 43918f1..4b9cdbc 100644 --- a/qobject/qnull.c +++ b/qobject/qnull.c @@ -18,3 +18,12 @@ QObject qnull_ = { .type = QTYPE_QNULL, .refcnt = 1, }; + +/** + * qnull_is_equal(): Always return true because any two QNull objects + * are equal. + */ +bool qnull_is_equal(const QObject *x, const QObject *y) +{ + return true; +} diff --git a/qobject/qnum.c b/qobject/qnum.c index 476e81c..784d061 100644 --- a/qobject/qnum.c +++ b/qobject/qnum.c @@ -213,6 +213,59 @@ QNum *qobject_to_qnum(const QObject *obj) } /** + * qnum_is_equal(): Test whether the two QNums are equal + */ +bool qnum_is_equal(const QObject *x, const QObject *y) +{ + QNum *num_x = qobject_to_qnum(x); + QNum *num_y = qobject_to_qnum(y); + + switch (num_x->kind) { + case QNUM_I64: + switch (num_y->kind) { + case QNUM_I64: + /* Comparison in native int64_t type */ + return num_x->u.i64 == num_y->u.i64; + case QNUM_U64: + /* Implicit conversion of x to uin64_t, so we have to + * check its sign before */ + return num_x->u.i64 >= 0 && num_x->u.i64 == num_y->u.u64; + case QNUM_DOUBLE: + /* Implicit conversion of x to double; no overflow + * possible */ + return num_x->u.i64 == num_y->u.dbl; + } + abort(); + case QNUM_U64: + switch (num_y->kind) { + case QNUM_I64: + return qnum_is_equal(y, x); + case QNUM_U64: + /* Comparison in native uint64_t type */ + return num_x->u.u64 == num_y->u.u64; + case QNUM_DOUBLE: + /* Implicit conversion of x to double; no overflow + * possible */ + return num_x->u.u64 == num_y->u.dbl; + } + abort(); + case QNUM_DOUBLE: + switch (num_y->kind) { + case QNUM_I64: + return qnum_is_equal(y, x); + case QNUM_U64: + return qnum_is_equal(y, x); + case QNUM_DOUBLE: + /* Comparison in native double type */ + return num_x->u.dbl == num_y->u.dbl; + } + abort(); + } + + abort(); +} + +/** * qnum_destroy_obj(): Free all memory allocated by a * QNum object */ diff --git a/qobject/qobject.c b/qobject/qobject.c index b0cafb6..b2a5360 100644 --- a/qobject/qobject.c +++ b/qobject/qobject.c @@ -27,3 +27,32 @@ void qobject_destroy(QObject *obj) assert(QTYPE_QNULL < obj->type && obj->type < QTYPE__MAX); qdestroy[obj->type](obj); } + + +static bool (*qis_equal[QTYPE__MAX])(const QObject *, const QObject *) = { + [QTYPE_NONE] = NULL, /* No such object exists */ + [QTYPE_QNULL] = qnull_is_equal, + [QTYPE_QNUM] = qnum_is_equal, + [QTYPE_QSTRING] = qstring_is_equal, + [QTYPE_QDICT] = qdict_is_equal, + [QTYPE_QLIST] = qlist_is_equal, + [QTYPE_QBOOL] = qbool_is_equal, +}; + +bool qobject_is_equal(const QObject *x, const QObject *y) +{ + /* We cannot test x == y because an object does not need to be + * equal to itself (e.g. NaN floats are not). */ + + if (!x && !y) { + return true; + } + + if (!x || !y || x->type != y->type) { + return false; + } + + assert(QTYPE_NONE < x->type && x->type < QTYPE__MAX); + + return qis_equal[x->type](x, y); +} diff --git a/qobject/qstring.c b/qobject/qstring.c index 5da7b5f..74182a1 100644 --- a/qobject/qstring.c +++ b/qobject/qstring.c @@ -129,6 +129,15 @@ const char *qstring_get_str(const QString *qstring) } /** + * qstring_is_equal(): Test whether the two QStrings are equal + */ +bool qstring_is_equal(const QObject *x, const QObject *y) +{ + return !strcmp(qobject_to_qstring(x)->string, + qobject_to_qstring(y)->string); +} + +/** * qstring_destroy_obj(): Free all memory allocated by a QString * object */
This generic function (along with its implementations for different types) determines whether two QObjects are equal. Signed-off-by: Max Reitz <mreitz@redhat.com> --- include/qapi/qmp/qbool.h | 1 + include/qapi/qmp/qdict.h | 1 + include/qapi/qmp/qlist.h | 1 + include/qapi/qmp/qnull.h | 2 ++ include/qapi/qmp/qnum.h | 1 + include/qapi/qmp/qobject.h | 9 ++++++++ include/qapi/qmp/qstring.h | 1 + qobject/qbool.c | 8 +++++++ qobject/qdict.c | 29 +++++++++++++++++++++++++ qobject/qlist.c | 32 ++++++++++++++++++++++++++++ qobject/qnull.c | 9 ++++++++ qobject/qnum.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++ qobject/qobject.c | 29 +++++++++++++++++++++++++ qobject/qstring.c | 9 ++++++++ 14 files changed, 185 insertions(+)