Closed
Bug 367673
Opened 18 years ago
Closed 17 years ago
Create and use NSCoordSaturatingAdd and NSCoordSaturatingSubtract (was: assertions with testcase that uses tablelayout: fixed)
Categories
(Core :: Layout: Tables, defect)
Core
Layout: Tables
Tracking
()
RESOLVED
FIXED
People
(Reporter: jruderman, Assigned: dholbert)
References
Details
(Keywords: assertion, testcase)
Attachments
(3 files, 9 obsolete files)
622 bytes,
application/xhtml+xml

Details  
19.38 KB,
patch

Details  Diff  Splinter Review  
19.38 KB,
patch

Details  Diff  Splinter Review 
###!!! 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•18 years ago


Hmm... So FixedTableLayoutStrategy::GetPrefWidth returns nscoord_Max. So the cell that contains the autowidth fixedlayout 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.
Flags: blocking1.9?
Flags: blocking1.9? → blocking1.9+
Assignee: nobody → dbaron
Assignee  
Comment 2•17 years ago


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.
Assignee  
Comment 3•17 years ago


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.)
Assignee  
Updated•17 years ago

Assignee: dbaron → dholbert
OS: Mac OS X → All
Assignee  
Updated•17 years ago

Status: NEW → ASSIGNED
Assignee  
Comment 4•17 years ago


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.
Attachment #278988 
Flags: review?(dbaron)
Reporter  
Comment 5•17 years ago


>+ * 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?
Assignee  
Comment 6•17 years ago


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.
Attachment #278988 
Attachment is obsolete: true
Attachment #279047 
Flags: review?(dbaron)
Attachment #278988 
Flags: review?(dbaron)
Reporter  
Comment 7•17 years ago


+ 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 :)
Assignee  
Comment 8•17 years ago


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.
Attachment #279047 
Attachment is obsolete: true
Attachment #279047 
Flags: review?(dbaron)
Assignee  
Comment 9•17 years ago


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 negativeoverflow 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 infinitewidth columns, this helps us divide up the width between them rather than assigning all of the width to the first one.
Assignee  
Comment 10•17 years ago


A few more changes in v4 of the patch:
1. Add/Subtract functions now expect nonnegative 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 nonnegative.
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 nonnegativity of its arguments, because an argument could be negative in that situation (specifically, negative marginwidth). 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.
Attachment #279172 
Attachment is obsolete: true
Assignee  
Comment 11•17 years ago


Are we still planning on moving to nscoords being floats?
If so, then I should add NSCOORD_IS_FLOAT cases to NSCoordAddCheckingMax and NSCoordSubtractCheckingMax.
Assignee  
Updated•17 years ago

Attachment #279639 
Flags: review?(dbaron)
Assignee  
Updated•17 years ago

Hardware: Macintosh → All
Assignee  
Comment 12•17 years ago


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.
Attachment #279639 
Attachment is obsolete: true
Attachment #279652 
Flags: review?(dbaron)
Attachment #279639 
Flags: review?(dbaron)
Assignee  
Comment 13•17 years ago


Found one more place where we need to call this patch's maxchecking add function.
This additional call helps fix bug 363722.
Attachment #279652 
Attachment is obsolete: true
Attachment #279652 
Flags: review?(dbaron)
Assignee  
Updated•17 years ago

Attachment #281238 
Flags: review?(dbaron)
I'd call these NSUnsignedCoordSaturatingAdd and NSUnsignedCoordSaturatingSubtract.
Assignee  
Updated•17 years ago

Attachment #281238 
Flags: review?(dbaron) → review?(roc)
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.
+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.
Assignee  
Comment 17•17 years ago


(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 specialcasing for subtraction after the switch to floats, because of the "infinity  infinity" case (see discussion of "infinityinfinity" below).
It's also nice to be able to depend on the nonnegative 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 "infinityinfinity", and also the PR_MAX to negativecheck N1N2, 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 infinitewidth) columns after we've subtracted out the width of one infinitewidth 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 boundschecking 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 "Ninfinity", we can remove that NOTREACHED. But for now I think it's a good idea to leave it in.
(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 infinitewidth)
> columns after we've subtracted out the width of one infinitewidth 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 boundschecking 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 "Ninfinity", we can remove that
> NOTREACHED. But for now I think it's a good idea to leave it in.
OK.
Assignee  
Comment 19•17 years ago


(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.
Assignee  
Comment 20•17 years ago


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.
Attachment #281238 
Attachment is obsolete: true
Attachment #281542 
Flags: review?(roc)
Attachment #281238 
Flags: review?(roc)
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.
Attachment #281542 
Flags: superreview+
Attachment #281542 
Flags: review?(roc)
Attachment #281542 
Flags: review+
Attachment #281542 
Flags: approval1.9+
Assignee  
Comment 22•17 years ago


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.
Attachment #281542 
Attachment is obsolete: true
Could you explain the handling of numInfiniteWidthCols to me? It seems like you're assuming that nscoord_MAX divides into nonnscoord_MAX numbers like infinity does, but that isn't really the case.
Assignee  
Comment 25•17 years ago


Here's the reason behind numInfiniteWidthCols:
The amount of extra width that we normally give out to each autowidth 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 prefwidth 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 infinitewidth 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 infinitewidth columns, instead of all going to the first one.
I think I may need to add one more case under FLEX_FLEX_SMALL for noninfinitewidth cols mixed in there, though... I have to go now, but I'll look at it later tonight or tomorrow morning.
Keywords: checkinneeded
Assignee  
Comment 26•17 years ago


From comment 25:
> I think I may need to add one more case under FLEX_FLEX_SMALL for
> noninfinitewidth cols mixed in there, though...
Added that case.
Attachment #281554 
Attachment is obsolete: true
Yep, that fixes the issue I was worried about.
But you might want to spell "using" correctly (not "usihng").
Assignee  
Comment 28•17 years ago


thanks for the typo correction. :)
Attachment #281701 
Attachment is obsolete: true
Assignee  
Comment 29•17 years ago


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
Assignee  
Updated•17 years ago

Status: ASSIGNED → RESOLVED
Closed: 17 years ago
Resolution:  → FIXED
Reporter  
Updated•17 years ago

Summary: Multiple assertions with testcase that uses tablelayout: fixed → Create and use NSCoordSaturatingAdd and NSCoordSaturatingSubtract (was: assertions with testcase that uses tablelayout: fixed)
You need to log in
before you can comment on or make changes to this bug.
Description
•