Closed Bug 847480 Opened 12 years ago Closed 11 years ago

Make mozilla::Abs return the corresponding unsigned type

Categories

(Core :: MFBT, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla22

People

(Reporter: Waldo, Assigned: Waldo)

References

Details

Attachments

(11 files, 1 obsolete file)

3.07 KB, patch
Ms2ger
: review+
Details | Diff | Splinter Review
29.75 KB, patch
Ms2ger
: review+
Details | Diff | Splinter Review
3.51 KB, patch
bjacob
: review+
Details | Diff | Splinter Review
9.50 KB, patch
Ms2ger
: review+
Details | Diff | Splinter Review
5.97 KB, patch
Ms2ger
: review+
Details | Diff | Splinter Review
3.22 KB, patch
nbp
: review+
Details | Diff | Splinter Review
1.51 KB, patch
mjrosenb
: review+
Details | Diff | Splinter Review
789 bytes, patch
dbaron
: review+
Details | Diff | Splinter Review
1.04 KB, patch
dbaron
: review+
Details | Diff | Splinter Review
1.23 KB, patch
Ms2ger
: review+
Details | Diff | Splinter Review
1.65 KB, patch
MatsPalmgren_bugz
: review+
Details | Diff | Splinter Review
abs, labs, llabs, and the std:: versions take the signed type T and return the signed type T.  The reason is apparently because of weird type promotion behavior: using a binary operator on an unsigned value and a signed value gives you an unsigned value back.

http://stackoverflow.com/questions/1610947/why-does-stdlib-hs-abs-family-of-functions-return-a-signed-value (oh hey, I recognize the question author :-) )

mozilla::Abs copies (well, will copy -- don't really want to delay that bug to consider this one, seems like we can change this or not after that lands) this right now.  I'm inclined to say we should change and make it return the corresponding unsigned type.  This eliminates the odd INT32_MIN edge case.  There is the cost of promotion behavior noted above.  But we have compiler warnings for that case, where we do not for the other.  That actually seems a *benefit* to this change.  And it seems more natural, in general, to have a (now-)guaranteed-nonnegative value have a type that's unsigned.

So, should we change this when we can?  Or should we leave it as-is?
Ms2ger, thoughts?  I'd like to do this, or not, before I start publicizing mozilla::Abs as the one true way, and before any sort of true concerted effort to convert the remaining abs() users in the tree (and not in external-ish code) to mozilla::Abs.  Also there'll be a little delay if this is done to audit callers keeping particularly in mind the promotion isue.
Flags: needinfo?(Ms2ger)
Doing this appears to make sense to me.
Flags: needinfo?(Ms2ger)
Summary: Consider making mozilla::Abs return the corresponding unsigned type → Make mozilla::Abs return the corresponding unsigned type
Auditing and fixing all the callers is going to take a little work.  I've fixed most of them in my tree, but some it's just really not obvious what should be done, if you're not familiar with the code.  So I think we should keep around the current behavior as DeprecatedAbs, create the desired behavior in Abs, and let both coexist until all deprecated computations have been converted.  This also lets us start advertising Abs as the one true way to do it, without holding up on conversions of existing code.
Assignee: nobody → jwalden+bmo
Status: NEW → ASSIGNED
Attachment #722418 - Flags: review?(Ms2ger)
The easy places that can be changed, I'll change in another patch.
Attachment #722419 - Flags: review?(Ms2ger)
Attachment #722420 - Flags: review?(Ms2ger)
Floating point types have no can't-absolutize edge cases, so they convert trivially.

Note that this doesn't handle nscoord cases when nscoord's compiled as a floating-point type.  Those cases need layout people to look at the patches.  :-)
Attachment #722423 - Flags: review?(Ms2ger)
Assignment to a type admitting all relevant absolute values is easy (usually this is to the unsigned type directly).  Comparison to a constant is easy.  A couple places, converting the use of the signed absolute to unsigned was easy.

Note that in xpfe/appshell/src/nsXULWindow.cpp kSlop is used only those places, so it's just a compare-to-constant case.
Attachment #722426 - Flags: review?(Ms2ger)
Attachment #722427 - Flags: review?(nicolas.b.pierron)
All these values are limited by the ARM architecture's constraints on these offsets.  Please double-check them for me!  (Especially the one I looked up, and added an assert for, myself.)
Attachment #722430 - Flags: review?(mrosenberg)
Attached patch Fix the nscoord cases (obsolete) — Splinter Review
I think the existing code might be buggy here, in that it assumes nscoord subtraction can't overflow.  Operating on floaty versions of the coords should do the trick.
Attachment #722432 - Flags: review?(dholbert)
Attachment #722427 - Flags: review?(nicolas.b.pierron) → review+
Comment on attachment 722430 [details] [diff] [review]
Fix ARM backend harder-ish cases

Review of attachment 722430 [details] [diff] [review]:
-----------------------------------------------------------------

You may also want to add in an assert for the vfp case.  The maximum offset is 1020 (255*4 for alignment)

::: js/src/ion/arm/Assembler-arm.h
@@ +791,5 @@
>    public:
>      EDtrOffImm(int32_t imm)
> +      : EDtrOff(datastore::Imm8Data(mozilla::Abs(imm)), (imm >= 0) ? IsUp : IsDown)
> +    {
> +        JS_ASSERT(mozilla::Abs(imm) < 4096);

The limit for the extended data transfer instructions is 255 bytes.
Attachment #722430 - Flags: review?(mrosenberg) → review+
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #0)
> There is the cost of promotion behavior noted above.  But we have compiler
> warnings for that case, where we do not for the other.

Are you sure that there are warnings for that?  IIRC, GCC 4.7 warns for signed/unsigned comparisons, but not for signed/unsigned values being used together in arithmetic.

(I'm not sure that this potential lack-of-warnings would be something that should block this, but it makes it less obvious that this is an improvement.)
Comment on attachment 722432 [details] [diff] [review]
Fix the nscoord cases

Punting review to Mats, because hg blame says he touched these lines very recently (just a few months ago), switching them from NS_ABS to std::abs, in bug 817574, so he might be interested in this change.
Attachment #722432 - Flags: review?(dholbert) → review?(matspal)
NS_GetLuminosity returns a value in the range [0, 255000], so the subtraction can be safely cast.  Looking at all the uses, I think the difference might only be used in places that could be better as uint32_t, but I'm not entirely sure.  This is the smallest change to move forward here; if you think more is desirable, and correct, I'm happy to make it.
Attachment #722484 - Flags: review?(dbaron)
font-stretch has a small range of enumerated values, so there's no worry of overflowing there.  In the other case we really need to do the initial subtraction in double-space, else we'll sometimes overflow/underflow and get nonsense distances, I think.
Attachment #722486 - Flags: review?(dbaron)
Wouldn't it make sense to make DeprecatedAbs be MOZ_DEPRECATED?
https://tbpl.mozilla.org/?tree=Try&rev=3d9b9407cc4c and https://tbpl.mozilla.org/?tree=Try&rev=55fe74cdfcca say these removals are fine.

After all these patches we're down to about 11 files still needing to change.  I think we want the signature changed enough to be able to take all these changes, then fix the remaining 11 files after that (if still in short order).  I may need to enlist more help for converting at least some of them, not entirely sure yet.
Attachment #722488 - Flags: review?(Ms2ger)
Unfortunately, we're warning-spammy enough that I think developers aren't going to immediately notice if they trigger a warning using a bad version.  The name has to change somehow if two versions are going to temporarily coexist (for not much longer than a week or so, I hope), and putting it in the name forces people to confront this.
(In reply to Daniel Holbert [:dholbert] from comment #13)
> Are you sure that there are warnings for that?  IIRC, GCC 4.7 warns for
> signed/unsigned comparisons, but not for signed/unsigned values being used
> together in arithmetic.
> 
> (I'm not sure that this potential lack-of-warnings would be something that
> should block this, but it makes it less obvious that this is an improvement.)

Hmm, I'd thought yes, but maybe I'm mistaken.  Given the fair number of places that assign abses to unsigned types, I think it's worthwhile even if there are fewer warnings than I'd thought.
Comment on attachment 722432 [details] [diff] [review]
Fix the nscoord cases

Review of attachment 722432 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/mathml/nsMathMLChar.cpp
@@ +747,4 @@
>    // or in sloppy markups without protective <mrow></mrow>
>    bool isNormal =
>      (aHint & NS_STRETCH_NORMAL)
> +    && bool(Abs(float(a) - float(b))

Actually, hmm.  uint32_t to float is lossy.  Maybe I should be using double instead, actually, for all these nscoord difference casts?
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #11)
> I think the existing code might be buggy here, in that it assumes nscoord
> subtraction can't overflow.  Operating on floaty versions of the coords
> should do the trick.

A few thoughts here:
 (a) I think the "nscoord subtraction can't overflow" assumption basically true, actually, for "valid" nscoord values. (where valid means "in the range of (nscoord_MIN, nscoord_MAX))  Once we're dealing with values that are larger than that, we'll get all sorts of layout problems, and it's not worth worrying about this specific case.

 (b) In light of 'a': if we still want to promote to a wider-range type, I'd think we should use int64_t instead of float, to avoid the lossiness mentioned in Comment 21 and to avoid unnecessary floating-point math.
Comment on attachment 722432 [details] [diff] [review]
Fix the nscoord cases

r- because the code is better as is.
Also, if you really need to fix nscoord overflow somewhere you should use
the NSCoordSaturating* functions in gfx/src/nsCoord.h, but in general you
shouldn't bother.
Attachment #722432 - Flags: review?(matspal) → review-
Attached patch nscoord, v2Splinter Review
Like this then, with no casts on the values in the subtractions?

The formatting is pretty funky here: && at the start of the line, unnecessary bool casts, and cast-to-float when the other component of the comparison or binary operation is already float (such that things will be done in floating point space anyway).  I figured probably best to leave them alone, but I can change if desired.
Attachment #722432 - Attachment is obsolete: true
Attachment #723016 - Flags: review?(matspal)
Comment on attachment 723016 [details] [diff] [review]
nscoord, v2

r=mats, feel free to fix the formatting and remove the redundant bool()
if you feel so inclined.  (no need to review that)
Attachment #723016 - Flags: review?(matspal) → review+
Comment on attachment 722418 [details] [diff] [review]
Copy mozilla::Abs to mozilla::DeprecatedAbs

Review of attachment 722418 [details] [diff] [review]:
-----------------------------------------------------------------

On the assumption that you can c/p, r=me.
Attachment #722418 - Flags: review?(Ms2ger) → review+
Comment on attachment 722419 [details] [diff] [review]
Blindly convert all Abs users to DeprecatedAbs

Review of attachment 722419 [details] [diff] [review]:
-----------------------------------------------------------------

Blind r=me.
Attachment #722419 - Flags: review?(Ms2ger) → review+
Comment on attachment 722420 [details] [diff] [review]
Give Abs the semantics we want

Review of attachment 722420 [details] [diff] [review]:
-----------------------------------------------------------------

This is something for someone who knows how ~ works :)
Attachment #722420 - Flags: review?(Ms2ger)
Comment on attachment 722423 [details] [diff] [review]
Convert floating-point cases

Review of attachment 722423 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM
Attachment #722423 - Flags: review?(Ms2ger) → review+
Comment on attachment 722426 [details] [diff] [review]
Change the easy cases

Review of attachment 722426 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM.
Attachment #722426 - Flags: review?(Ms2ger) → review+
Comment on attachment 722488 [details] [diff] [review]
Remove a bunch of DeprecatedAbs overloads, so people won't ignore the name and use it anyway for some stuff

Review of attachment 722488 [details] [diff] [review]:
-----------------------------------------------------------------

r=me.
Attachment #722488 - Flags: review?(Ms2ger) → review+
Attachment #722420 - Flags: review?(bjacob)
Comment on attachment 722420 [details] [diff] [review]
Give Abs the semantics we want

Review of attachment 722420 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/MathAlgorithms.h
@@ +125,2 @@
>  
> +template<> struct AbsReturnTypeFixed<int8_t> { typedef uint8_t Type; };

I'm scared of Abs(T) returning the unsigned variant of T, instead of T itself.

It's unlike std::abs; it could easily lead to gratuitous warnings about mixing signed with unsigned in expressions where it will be used; and it can't apply anyway to floating-point types.

Was there a solid rationale for this change?

@@ +125,5 @@
>  
> +template<> struct AbsReturnTypeFixed<int8_t> { typedef uint8_t Type; };
> +template<> struct AbsReturnTypeFixed<int16_t> { typedef uint16_t Type; };
> +template<> struct AbsReturnTypeFixed<int32_t> { typedef uint32_t Type; };
> +template<> struct AbsReturnTypeFixed<int64_t> { typedef uint64_t Type; };

Please add specializations for unsigned types, as generic code could easily find itself instantiated in a way that makes it call Abs on unsigned types.

@@ +138,5 @@
> +template<> struct AbsReturnType<long> { typedef unsigned long Type; };
> +template<> struct AbsReturnType<long long> { typedef unsigned long long Type; };
> +template<> struct AbsReturnType<float> { typedef float Type; };
> +template<> struct AbsReturnType<double> { typedef double Type; };
> +template<> struct AbsReturnType<long double> { typedef long double Type; };

Same here.

@@ +148,4 @@
>  Abs(const T t)
>  {
> +  typedef typename detail::AbsReturnType<T>::Type ReturnType;
> +  return t >= 0 ? ReturnType(t) : ~ReturnType(t) + 1;

Why are you replacing (-t) by (~ReturnType(t) + 1) here? It looks like a more arcane way of computing the same thing; it could also be compiled to two instructions instead of one.

If you use (-t) and allow unsigned types, you will get MSVC warnings, but that is easy to fix as we did in CheckedInt there:
  http://dxr.mozilla.org/mozilla-central/mfbt/CheckedInt.h#l453
you could even reuse OppositeIfSignedImpl. In fact, that helper could be renamed just "Abs" ;-)

@@ -157,5 @@
> -  // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
> -  // (minvalue + 1) == -maxvalue).
> -  MOZ_ASSERT(t >= 0 ||
> -             -(t + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
> -             "You can't negate the smallest possible negative integer!");

Is the removal of this assertion intentional? If yes, that's OK as std::abs wouldn't perform this check, and CheckedInt is here for that anyway. But I want to know if it's intentional.
Attachment #722420 - Flags: review?(bjacob) → review-
Comment on attachment 722420 [details] [diff] [review]
Give Abs the semantics we want

Judging by your comments as a whole, I think you weren't aware of the minimum-value case that motivates this change as a whole, so I'm requesting you reconsider.

(In reply to Benoit Jacob [:bjacob] from comment #32)
> It's unlike std::abs; it could easily lead to gratuitous warnings about
> mixing signed with unsigned in expressions where it will be used; and it
> can't apply anyway to floating-point types.
> 
> Was there a solid rationale for this change?

If std::abs returns the same type, it can't work on every input value.  abs(int) can't work on INT_MIN, abs(int32_t) can't work on INT32_MIN, and so on.  Not considering this leads to bugs.  I've found three such bugs in Gecko without really trying and expect to find more with ease.  Abs semantics should match mathematical intuition without this edge case.

Warnings are also a virtue because they're more immediately visible than an assertion that'll botch only if one particular likely-uncommon value flows through.

The floating-point overloads work on every input value, so they'll be unchanged when everything's fixed here.  It's *more* consistent for abs(signed-type) to work in all cases like abs(floating-type) does.

> Please add specializations for unsigned types, as generic code could easily
> find itself instantiated in a way that makes it call Abs on unsigned types.

It's a category error to compute the absolute of an unsigned value.  std::abs only has overloads that take signed or floating types: passing unsigned to std::abs often results in *double-typed* values now.  We shouldn't design this for generic code: it's not the common case.  I plan to fill out mozilla::Is{Uns,S}igned<T>::value in TypeTraits.h to handle this more easily, eventually.

> If you use (-t) and allow unsigned types, you will get MSVC warnings

This was the reason.  I could comment, but as this is write-once, use-forever, it seemed unimportant.

> but that is easy to fix as we did in CheckedInt there:
>   http://dxr.mozilla.org/mozilla-central/mfbt/CheckedInt.h#l453
> you could even reuse OppositeIfSignedImpl. In fact, that helper could be
> renamed just "Abs" ;-)

Your "easy fix" invokes undefined behavior in evaluating |-x| for the signed case.  C++98 5 Expressions, [expr]p5:

> If during the evaluation of an expression, the result is not
> mathematically defined or not in the range of representable values for
> its type, the behavior is undefined

Which, given we ran that test through compilers that would error out on undefined behavior, makes me bet we have no CheckedInt::operator-() tests for the minimum value of a signed type.

> @@ -157,5 @@
> > -  // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
> > -  // (minvalue + 1) == -maxvalue).
> > -  MOZ_ASSERT(t >= 0 ||
> > -             -(t + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
> > -             "You can't negate the smallest possible negative integer!");
> 
> Is the removal of this assertion intentional? If yes, that's OK as std::abs
> wouldn't perform this check, and CheckedInt is here for that anyway. But I
> want to know if it's intentional.

It's intentional.  When an unsigned type's returned, it's no problem to negate the minimum signed value.  It *is* a problem if that negation must fit in the same-size signed type, which is precisely what motivates this change.

It really is unfortunate that std::abs doesn't perform this check and abort/assert/fail hard.  If it had, those bugs I mentioned would have been detected much sooner.
Attachment #722420 - Flags: review- → review?(bjacob)
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #33)
> Comment on attachment 722420 [details] [diff] [review]
> Give Abs the semantics we want
> 
> Judging by your comments as a whole, I think you weren't aware of the
> minimum-value case that motivates this change as a whole, so I'm requesting
> you reconsider.

I'm aware of the minimum-value case, but didn't realize that it motivated this whole change.

> 
> (In reply to Benoit Jacob [:bjacob] from comment #32)
> > It's unlike std::abs; it could easily lead to gratuitous warnings about
> > mixing signed with unsigned in expressions where it will be used; and it
> > can't apply anyway to floating-point types.
> > 
> > Was there a solid rationale for this change?
> 
> If std::abs returns the same type, it can't work on every input value. 
> abs(int) can't work on INT_MIN, abs(int32_t) can't work on INT32_MIN, and so
> on.  Not considering this leads to bugs.  I've found three such bugs in
> Gecko without really trying and expect to find more with ease.

Hm. OK. I realize that an assertion here isn't enough to ensure safety, as the integer overflow may only be hit in the real world in runtime conditions that aren't covered by unit tests run on debug builds.

But I'm not sure that just returning unsigned here will buy you that much safety. If users of mozilla::Abs find that they get mixing-signed-and-unsigned warnings, they may naively 'fix' them in the trivial way by casting the return value of mozilla::Abs to signed...

In the end, to really prevent integer overflow, there may be no other way than doing runtime checks even in non-debug builds, like CheckedInt does.

> Abs
> semantics should match mathematical intuition without this edge case.

Maybe?... I don't know hard rules for how to balance good mathematical rigor vs floating-point reality...

> 
> Warnings are also a virtue because they're more immediately visible than an
> assertion that'll botch only if one particular likely-uncommon value flows
> through.

Until we've turn warnings-as-errors everywhere, warnings can be ignored too.

> 
> The floating-point overloads work on every input value, so they'll be
> unchanged when everything's fixed here.  It's *more* consistent for
> abs(signed-type) to work in all cases like abs(floating-type) does.

OK.

> 
> > Please add specializations for unsigned types, as generic code could easily
> > find itself instantiated in a way that makes it call Abs on unsigned types.
>
> It's a category error to compute the absolute of an unsigned value. 
> std::abs only has overloads that take signed or floating types: passing
> unsigned to std::abs often results in *double-typed* values now.

Wow -- I had no idea about that.

>  We
> shouldn't design this for generic code: it's not the common case.  I plan to
> fill out mozilla::Is{Uns,S}igned<T>::value in TypeTraits.h to handle this
> more easily, eventually.
> 
> > If you use (-t) and allow unsigned types, you will get MSVC warnings
> 
> This was the reason.  I could comment, but as this is write-once,
> use-forever, it seemed unimportant.
> 
> > but that is easy to fix as we did in CheckedInt there:
> >   http://dxr.mozilla.org/mozilla-central/mfbt/CheckedInt.h#l453
> > you could even reuse OppositeIfSignedImpl. In fact, that helper could be
> > renamed just "Abs" ;-)
> 
> Your "easy fix" invokes undefined behavior in evaluating |-x| for the signed
> case.  C++98 5 Expressions, [expr]p5:
> 
> > If during the evaluation of an expression, the result is not
> > mathematically defined or not in the range of representable values for
> > its type, the behavior is undefined
> 
> Which, given we ran that test through compilers that would error out on
> undefined behavior, makes me bet we have no CheckedInt::operator-() tests
> for the minimum value of a signed type.

CheckedInt's unary operator- doesn't have this bug because it correctly marks the result as invalid in this case, performing the same check as in binary (0 - minvalue):

http://dxr.mozilla.org/mozilla-central/mfbt/CheckedInt.h#l625

But we could use a more explicit, specific test for this form.
Comment on attachment 722420 [details] [diff] [review]
Give Abs the semantics we want

r+ given the change is coherently motivated.
Attachment #722420 - Flags: review?(bjacob) → review+
(In reply to Benoit Jacob [:bjacob] from comment #34)
> > Which, given we ran that test through compilers that would error out on
> > undefined behavior, makes me bet we have no CheckedInt::operator-() tests
> > for the minimum value of a signed type.
> 
> CheckedInt's unary operator- doesn't have this bug because it correctly
> marks the result as invalid in this case, performing the same check as in
> binary (0 - minvalue):
> 
> http://dxr.mozilla.org/mozilla-central/mfbt/CheckedInt.h#l625
> 
> But we could use a more explicit, specific test for this form.

D'oh! ... even if CheckedInt is formally correct here as the result is an invalid CheckedInt, using this undefined behavior is a bug as the compiler could miscompile undefined-behavior code arbitrarily (i.e. decide it means reboot the computer). So yes we have a bug here. A unit test wouldnt catch it though, except if running in IOC. One weird thing though, we do have some tests that should exercise that such as the one with 0 - min + min. Will look.
Comment on attachment 722486 [details] [diff] [review]
Fix animation Abs

r=dbaron, though neither the old nor the new code actually produces correct results in all cases in which they could be produced
Attachment #722486 - Flags: review?(dbaron) → review+
Comment on attachment 722484 [details] [diff] [review]
Convert NS_LUMINOSITY to unsigned Abs

r=dbaron
Attachment #722484 - Flags: review?(dbaron) → review+
Not knowing exactly when I'll have time to sort through the remaining DeprecatedAbs uses, I think I'll just close this and deal with those elsewhere.  There aren't too many uses, and hopefully the name will scare people off, and mozilla::Abs is ready for use and publicized, so it seems not too important holding this up for trailing fixes any more.
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Whiteboard: [leave open]
Target Milestone: --- → mozilla22
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: