367673 - Create and use NSCoordSaturatingAdd and NSCoordSaturatingSubtract (was: assertions with testcase that uses table-layout: fixed)

Status: RESOLVED FIXED

(Core :: Layout: Tables, defect)

Description

[Jesse Ruderman]

Attachment: testcase

###!!! ASSERTION: wrong case: 'colFrame->GetHasSpecifiedCoord() || colFrame->GetPrefCoord() == 0', file /Users/admin/trunk/mozilla/layout/tables/BasicTableLayoutStrategy.cpp, line 866

###!!! ASSERTION: assigned width smaller than min: 'col_width >= colFrame->GetMinCoord()', file /Users/admin/trunk/mozilla/layout/tables/BasicTableLayoutStrategy.cpp, line 881

###!!! ASSERTION: Computed overflow area must contain frame bounds: 'aNewSize.width == 0 || aNewSize.height == 0 || aOverflowArea->Contains(nsRect(nsPoint(0, 0), aNewSize))', file /Users/admin/trunk/mozilla/layout/generic/nsFrame.cpp, line 5260

Comment 1

[Boris Zbarsky [:bzbarsky]]

Hmm...  So FixedTableLayoutStrategy::GetPrefWidth returns nscoord_Max.  So the cell that contains the auto-width fixed-layout table claims nscoord_Max as its preferred width.  Then GetCellWidthInfo() returns that as the pref width, and we end up setting:

(gdb) p colFrame->mMinCoord
$14 = 140
(gdb) p colFrame->mPrefCoord
$15 = 1073741914

on the column.

Then when we compute guess_pref we add two of those plus the pref width for the third cell, and overflow nscoord.  So we end up with a guess_pref of -2147483006. From that, I bet we compute the wrong l2t, etc.

Comment 2

[Daniel Holbert [:dholbert]]

Attachment: patch (using NSCoordAddCheckingMax)

Made inline functions "NSCoordAddCheckingMax" and "NSCoordSubtractCheckingMax" to do nscoord_MAX arithmetic checks.

The idea is:
 nscoord_MAX + anything     ---> nscoord_MAX
 nscoord_MAX - anything     ---> nscoord_MAX
 
 anythingElse - nscoord_MAX ---> nscoord_MIN
 
Here, "anything" includes nscoord_MAX, but "anythingElse" does not.

There are probably more places in the code where we need to use this function (or something similar) -- I've added it in all the places I've found that need it so far.

Comment 3

[Daniel Holbert [:dholbert]]

Note: There are also two places where this patch changes an assertion 
  "x == 0" 
to 
  "x == 0 || x == nscoord_MAX".
(where "x" is "info.prefCoord" in one place and "basis.c" in the other)

This is needed because if x is nscoord_MAX, then NSCoordSubtractCheckingMax will never reduce its size. (Intuitively, when we have an infinite amount of width to distribute, then we still have an infinite amount left after we've distributed some of it.)

Comment 4

[Daniel Holbert [:dholbert]]

Comment on attachment 278988 [details] [diff] [review]
patch (using NSCoordAddCheckingMax)

Patch passes reftests.

cbarrett pointed out that it'd be possible to use a macro instead of an inline function to implement the add/subtract functions.  I'm not too familiar with the relative benefits/drawbacks of macros vs. inline, so let me know if that'd be a better solution.

Comment 5

[Jesse Ruderman]

>+ * Note: This function doesn't handle cases where 
>+ *    a < nscoord_MAX  and  b < nscoord_MAX  but  a+b > nscoord_MAX

Perhaps it should have an assertion to that effect?

Comment 6

[Daniel Holbert [:dholbert]]

Attachment: patch v2 (added assertions & call add func in one more place)

Good call, Jesse.  I added that assertion and a few more to the add/subtract functions.  I also put NSCoordAddCheckingMax in one additional place place that I discovered via that assertion.

Comment 7

[Jesse Ruderman]

+  NS_ASSERTION(a == nscoord_MAX || b == nscoord_MAX ||
+               (long)a + (long)b < (long)nscoord_MAX,
+               "Adding an nscoord near (but not equal to) nscoord_MAX");

I'd use a more precise assertion message, such as "nscoord addition will hit or pass nscoord_MAX".

It might be good to check for overflows in the negative direction too, and do the same thing in the subtract function.

> +  NS_ASSERTION(

This won't compile :)

Comment 8

[Daniel Holbert [:dholbert]]

Comment on attachment 279047 [details] [diff] [review]
patch v2 (added assertions & call add func in one more place)

> This won't compile :)

Oops! Thanks for catching that.  No idea how that made it through -- I thought I recompiled before posting the patch.

Posting a new patch with that and a few other changes soon.

Comment 9

[Daniel Holbert [:dholbert]]

Attachment: patch v3

Here are the major changes in this new version of the patch:

 1. It compiles. :)

 2. Replaced "-nscoord_MAX" with "nscoord_MIN", because those are equal.

 3. Added negative-overflow checks, per Jesse's suggestion

 4. Moved addition/subtraction overflow checks into the clauses where we actually do addition/subtraction, rather than at the beginning of the functions.

 5. Added "numInfiniteWidthCols" variable to BasicLayoutStrategy::ComputeColumnWidths.  Basically, in cases where we have infinite-width columns, this helps us divide up the width between them rather than assigning all of the width to the first one.

Comment 10

[Daniel Holbert [:dholbert]]

Attachment: patch v4

A few more changes in v4 of the patch:

  1. Add/Subtract functions now expect non-negative arguments. (with assertions to this effect)  This assumption is useful because it reduces the number of special cases we need to check for, speeding up execution.  This assumption is also pretty safe because these functions are used for math on widths, and widths should be non-negative.

  2. The [something - infinity] case in the subtract function now triggers a NS_NOTREACHED, because I don't think we should ever get in a situation where we'd want to perform that calculation.  That case now returns 0 instead of nscoord_MIN, because 0 seems like a safer value there.

  3. Added PR_MAX(0, xxx) to one call of NSCoordAddCheckingMax, to ensure the non-negativity of its arguments, because an argument could be negative in that situation (specifically, negative margin-width).  This makes sense, because this computation is for an intrinsic width in nsLayoutUtils::IntrinsicForContainer, and it previously resulted in a negative value for that intrinsic width.  And a negative intrinsic width is nonsensical, afaik.**

This patch passes the layout reftests, without any of the patch's asserts firing.

** Note: If I'm right that negative intrinsic widths are nonsensical, we might add an assert(result >= 0) at the end of nsLayoutUtils::IntrinsicForContainer.

Comment 11

[Daniel Holbert [:dholbert]]

Are we still planning on moving to nscoords being floats? 

If so, then I should add NSCOORD_IS_FLOAT cases to NSCoordAddCheckingMax and NSCoordSubtractCheckingMax.

Comment 12

[Daniel Holbert [:dholbert]]

Attachment: patch v5 (added NS_COORD_IS_FLOAT optimization)

One last change:  Added optimization for NS_COORD_IS_FLOAT case.

With floats, the only cases we have to explicitly define are:
 *  infinity - infinity       (which would produce NAN)
 *  somethingElse - infinity  (which would produce -infinity)

All the other cases from my add/subtract functions are handled correctly by normal float math.

Comment 13

[Daniel Holbert [:dholbert]]

Attachment: patch v6 (calling add function in one more place)

Found one more place where we need to call this patch's max-checking add function.  

This additional call helps fix bug 363722.

Comment 14

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I'd call these NSUnsignedCoordSaturatingAdd and NSUnsignedCoordSaturatingSubtract.

Comment 15

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The idea with float nscoords is that we'd use IEEE +Inf/-Inf for nscoord_MAX/MIN, so regular float arithmetic would always saturate, and we wouldn't need these functions. That is actually one of the main advantages of using floats. But that's off the table for the forseeable future. The comments in the patch need to be tweaked slightly to reflect this, though.

Comment 16

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+inline nscoord
+NSCoordAddCheckingMax(const nscoord a, const nscoord b)

Making these const is a bit pointless.

How about implementing NSUnsignedCoordSaturatingAdd for integers as
  PRUint32 sum = PRUint32(a) + PRUint32(b);
  return nscoord(PR_MIN(nscoord_MAX, sum));
? That way you handle overflow in general, not just the case when one of a and b is nscoord_MAX.

I'm not really sure what the behaviour of the subtract function should be. I think treating infinity - infinity is a mistake. (In IEEE this returns a NaN.) I think probably we need separate functions for separate behaviours, and we need to think about which behaviour is needed at each call site. I think it should clamp below at zero. So here are the possibilities:
-- infinity - N -> infinity
-- N1 - N2 -> PR_MAX(N1 - N2, 0)
-- N - infinity -> 0
-- infinity - infinity -> no idea ... how about having two versions, one which treats this simply as an error, and another that takes a value passed in by the caller for this case, so the caller can specify infinity or zero.

Comment 17

[Daniel Holbert [:dholbert]]

(In reply to comment #14)
> I'd call these NSUnsignedCoordSaturatingAdd and
> NSUnsignedCoordSaturatingSubtract.

Cool, I like those names and will change that.


(In reply to comment #15)
> The idea with float nscoords is that we'd use IEEE +Inf/-Inf for
> nscoord_MAX/MIN, so regular float arithmetic would always saturate, and we
> wouldn't need these functions.

I'd probably agree for the addition function, but we'll still need some sort of special-casing for subtraction after the switch to floats, because of the "infinity - infinity" case (see discussion of "infinity-infinity" below).

It's also nice to be able to depend on the non-negative assertion checks in those functions, but those are more for debugging and mostly don't affect the actual computation.


(In reply to comment #16)
> +inline nscoord
> +NSCoordAddCheckingMax(const nscoord a, const nscoord b)
> 
> Making these const is a bit pointless.

Well, basically, yeah... I was taught, as a matter of style and safety, to use const args unless you need to modify them.  I also thought I learned once that compiler optimizations could sometimes take advantage of "const", but I might have made that part up.

Anyway, I know that "const" doesn't make a big difference here, and I'm happy to take out the consts if you'd like.


> How about implementing NSUnsignedCoordSaturatingAdd for integers as
>   PRUint32 sum = PRUint32(a) + PRUint32(b);
>   return nscoord(PR_MIN(nscoord_MAX, sum));
> ? That way you handle overflow in general, not just the case when one of a and
> b is nscoord_MAX.

That wouldn't handle the (nscoord_MAX + nscoord_MAX) case, which would overflow and mess up the PR_MIN calculation.

Also, one of the principles behind this function is that we *shouldn't* be doing math with numbers that are in the neighborhood of nscoord_MAX.  The idea is that a+b = a+b, unless either a or b is inf, in which case a+b = inf.

As a side note, if we end up calling NSUnsignedCoordSaturatingAdd on a nscoord in the neighborhood of nscoord_MAX, then either...
  a) the big nscoord was created by doing arithmetic on nscoord_MAX
  b) the big nscoord is legitimately that big

  If (a) is the case, then we've doing normal arithmetic somewhere when we should have used NSUnsignedCoordSaturatingAdd.
  If (b) is the case, then we've got issues, because nscoord_MAX is a sentinel, which means it (and by extension, its neighborhood) should never be reached (or surpassed) by normal computations.

In either of those cases, we'd fail assertions in NSUnsignedCoordSaturatingAdd and would be able to track down the problem.

So anyway, I think I still like the "Add" implementation in my patch, but let me know if you disagree.


> I'm not really sure what the behaviour of the subtract function should be. I
> think treating infinity - infinity is a mistake. (In IEEE this returns a NaN.)
> I think probably we need separate functions for separate behaviours, and we
> need to think about which behaviour is needed at each call site. I think it
> should clamp below at zero. So here are the possibilities:
> -- infinity - N -> infinity
> -- N1 - N2 -> PR_MAX(N1 - N2, 0)
> -- N - infinity -> 0
> -- infinity - infinity -> no idea ... how about having two versions, one which
> treats this simply as an error, and another that takes a value passed in by the
> caller for this case, so the caller can specify infinity or zero.

Those behaviors are all implemented in the patch, with the exception of having two versions for "infinity-infinity", and also the PR_MAX to negative-check N1-N2, which I'll add.

Regarding "infinity - infinity":  virtually all of the times that I've come across this computation, it's for something like this:
    totalPrefWidths = totalPrefWidths - colPrefWidth
And I'd argue that nscoord_MAX is the correct answer to that computation, because we need to leave width around for other (possibly infinite-width) columns after we've subtracted out the width of one infinite-width column.

Anyway, I'll add a flag to distinguish between the two behaviors for "infinity - infinity".  I think I'll have it default to returning infinity, if you don't object, because that's what we'd want in all the cases I've seen where that computation might come up.

I also think the "N - infinity" case should trigger a NOTREACHED (in addition to returning 0), as it stands in the patch right now.  In my tests, the only time I've hit that case was when "N" was actually nscoord_MAX +/- some_small_delta, and the NOTREACHED helped me trace back to another place where we needed to do bounds-checking when generating N.  (Those cases are now fixed, thanks to this NOTREACHED.)  I don't think we should ever need to *legitimately* subtract "N - infinity" when doing height/width computations...  If it turns out that we do, or if we start using this function for other purposes that need to legitimately compute "N-infinity", we can remove that NOTREACHED.  But for now I think it's a good idea to leave it in.

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #17)
> (In reply to comment #16)
> > +inline nscoord
> > +NSCoordAddCheckingMax(const nscoord a, const nscoord b)
> > 
> > Making these const is a bit pointless.
> 
> Well, basically, yeah... I was taught, as a matter of style and safety, to use
> const args unless you need to modify them.

If it's a pointer or reference to something const, sure. But for direct parameters like this, it makes no difference to the caller whether they're const or not --- the callee can't modify anything in the caller, either way --- so it's not worth having them.

> I also thought I learned once that
> compiler optimizations could sometimes take advantage of "const", but I might
> have made that part up.

In this case it's trivial for the compiler to look at the function body and figure out for itself whether you modify them or not.

> Anyway, I know that "const" doesn't make a big difference here, and I'm happy
> to take out the consts if you'd like.

Please.

> > How about implementing NSUnsignedCoordSaturatingAdd for integers as
> >   PRUint32 sum = PRUint32(a) + PRUint32(b);
> >   return nscoord(PR_MIN(nscoord_MAX, sum));
> > ? That way you handle overflow in general, not just the case when one of a and
> > b is nscoord_MAX.
> 
> That wouldn't handle the (nscoord_MAX + nscoord_MAX) case, which would overflow
> and mess up the PR_MIN calculation.

No it won't. nscoord_MAX is 2^30, so the sume will be 2^31.

> Also, one of the principles behind this function is that we *shouldn't* be
> doing math with numbers that are in the neighborhood of nscoord_MAX.  The idea
> is that a+b = a+b, unless either a or b is inf, in which case a+b = inf.

It's fine to violate that here, in code that knows the details of how nscoord is implemented.

> As a side note, if we end up calling NSUnsignedCoordSaturatingAdd on a nscoord
> in the neighborhood of nscoord_MAX, then either...
>   a) the big nscoord was created by doing arithmetic on nscoord_MAX
>   b) the big nscoord is legitimately that big
> 
>   If (a) is the case, then we've doing normal arithmetic somewhere when we
> should have used NSUnsignedCoordSaturatingAdd.
>   If (b) is the case, then we've got issues, because nscoord_MAX is a sentinel,
> which means it (and by extension, its neighborhood) should never be reached (or
> surpassed) by normal computations.

It all depends on what you mean by "the neighbourhood". Wherever you draw a line between "valid" and "invalid" nscoords, someone can create a page that has valid metrics on either side of that line. So IMHO we may as well draw it at nscoord_MAX.

> Regarding "infinity - infinity":  virtually all of the times that I've come
> across this computation, it's for something like this:
>     totalPrefWidths = totalPrefWidths - colPrefWidth
> And I'd argue that nscoord_MAX is the correct answer to that computation,
> because we need to leave width around for other (possibly infinite-width)
> columns after we've subtracted out the width of one infinite-width column.
> 
> Anyway, I'll add a flag to distinguish between the two behaviors for "infinity
> - infinity".  I think I'll have it default to returning infinity, if you don't
> object, because that's what we'd want in all the cases I've seen where that
> computation might come up.

Pass an nscoord instead of a PRBool. I would prefer to have no default so that callers have to think about this.

> I also think the "N - infinity" case should trigger a NOTREACHED (in addition
> to returning 0), as it stands in the patch right now.  In my tests, the only
> time I've hit that case was when "N" was actually nscoord_MAX +/-
> some_small_delta, and the NOTREACHED helped me trace back to another place
> where we needed to do bounds-checking when generating N.  (Those cases are now
> fixed, thanks to this NOTREACHED.)  I don't think we should ever need to
> *legitimately* subtract "N - infinity" when doing height/width computations... 
> If it turns out that we do, or if we start using this function for other
> purposes that need to legitimately compute "N-infinity", we can remove that
> NOTREACHED.  But for now I think it's a good idea to leave it in.

OK.

Comment 19

[Daniel Holbert [:dholbert]]

(In reply to comment #18)
> If it's a pointer or reference to something const, sure. But for direct
> parameters like this, it makes no difference to the caller whether they're
> const or not --- the callee can't modify anything in the caller, either way 

Agreed -- I meant that it makes a difference to the callee, not the caller -- i.e. for args that don't need to change, const would protect against accidentally modifying the args early in the callee, which could affect code further down in the callee.

But that's not really a concern here, as the functions are teeny, so I'm happy to see the consts go.

> No it won't. nscoord_MAX is 2^30, so the sume will be 2^31.

Oops, I overlooked the U's in "PRUint32" -- I read "PRInt32", which would overflow.  Right you are.

> It's fine to violate that here, in code that knows the details of how nscoord
> is implemented.

OK.  I'll change the implementation, but leave in some assertions that warn about args in the neighborhood of nscoord_MAX.

> Pass an nscoord instead of a PRBool. I would prefer to have no default so that
> callers have to think about this.

Sounds good.

Comment 20

[Daniel Holbert [:dholbert]]

Attachment: patch v7 (addressed review comments)

Addressed review comments, with these amendments that roc and I talked about in IRC:

 1) Removed "Unsigned" from add/subtract function names, because pref width calculations do in fact occasionally involve negative widths.  E.g. if margins are negative, that gets incorporated into pref width computation in nsLayoutUtils::IntrinsicForContainer.  (However, afaik, the negative args should always be finite -- we don't expect to receive nscoord_MIN.)

 2) As a result of (1), kept original strategy for addition rather than the PRUint32 casting version, because the original strategy handles finite negative numbers.

This patch passes reftests, without causing new assertions.

Comment 21

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 281542 [details] [diff] [review]
patch v7 (addressed review comments)

+  // Integer nscoord --> Need special case for adding infinity.
+  if (a == nscoord_MAX || b == nscoord_MAX) {
+    return nscoord_MAX;
+  }

Sorry, I got confused. I still want to actually saturate if a + b > nscoord_MAX. So I'd like an additional PR_MIN(nscoord_MAX, a + b) here.

Comment 22

[Daniel Holbert [:dholbert]]

Attachment: patch v7b (ready for check-in)

Added a PR_MIN call in each function to cap the results of addition/subtraction for integer nscoords.

This version is ready for check in.

Comment 23

[Daniel Holbert [:dholbert]]

Checkin needed on "patch v7b"

Comment 24

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Could you explain the handling of numInfiniteWidthCols to me?  It seems like you're assuming that nscoord_MAX divides into non-nscoord_MAX numbers like infinity does, but that isn't really the case.

Comment 25

[Daniel Holbert [:dholbert]]

Here's the reason behind numInfiniteWidthCols:


The amount of extra width that we normally give out to each auto-width column in the FLEX_FLEX_SMALL case breaks down to this:
  (pref_minus_min / basis.c) * totalSpace
where basis.c is just the sum of all the pref_minus_min values across all columns.

In other words, we're giving each column "its share" of the total excess space, where "its share" is just 
   "how much extra it wants" / "total extra wanted by all columns."

However, if one or more columns have their pref-width being infinite, then
    (prefMinusMin / basis.c) * totalSpace
 is
    (nscoord_MAX/ nscoord_MAX) * totalSpace
 which is just
     1 * totalSpace

So the first such column will get *all* the width, and the others will get none of the width.  This is hardly fair.

The numInfiniteWidthCols variable is intended to assign each infinite-width column 
    (prefMinusMin / basis.c / numInfiniteWidthCols) * totalSpace
      which is
    (nscoord_MAX / nscoord_MAX / numInfiniteWidthCols) * totalSpace
      which is
    (totalSpace / numInfiniteWidthCols)

This lets the total space be distributed equally among the infinite-width columns, instead of all going to the first one.


I think I may need to add one more case under FLEX_FLEX_SMALL for non-infinite-width cols mixed in there, though... I have to go now, but I'll look at it later tonight or tomorrow morning.

Comment 26

[Daniel Holbert [:dholbert]]

Attachment: patch v7c (more explicit handling of cols under FLEX_FLEX_SMALL)

From comment 25:
> I think I may need to add one more case under FLEX_FLEX_SMALL for
> non-infinite-width cols mixed in there, though...

Added that case.

Comment 27

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Yep, that fixes the issue I was worried about.

But you might want to spell "using" correctly (not "usihng").

Comment 28

[Daniel Holbert [:dholbert]]

Attachment: patch v7d (s/usihng/using)

thanks for the typo correction. :)

Comment 29

[Daniel Holbert [:dholbert]]

Attachment: patch v7e, as landed (changed a float "0" to "0.0")

Checking in gfx/public/nsCoord.h;
/cvsroot/mozilla/gfx/public/nsCoord.h,v  <--  nsCoord.h
new revision: 1.9; previous revision: 1.8
done
Checking in layout/base/nsLayoutUtils.cpp;
/cvsroot/mozilla/layout/base/nsLayoutUtils.cpp,v  <--  nsLayoutUtils.cpp
new revision: 3.112; previous revision: 3.111
done
Checking in layout/generic/nsFrame.cpp;
/cvsroot/mozilla/layout/generic/nsFrame.cpp,v  <--  nsFrame.cpp
new revision: 3.755; previous revision: 3.754
done
Checking in layout/tables/BasicTableLayoutStrategy.cpp;
/cvsroot/mozilla/layout/tables/BasicTableLayoutStrategy.cpp,v  <--  BasicTableLayoutStrategy.cpp
new revision: 3.258; previous revision: 3.257
done

Comment 30

[Jesse Ruderman]

Crashtest checked in.