Closed Bug 1176621 Opened 7 years ago Closed 6 years ago

[css-grid] Implement "Stretch Flexible Tracks" and associated algorithms.

Categories

(Core :: Layout, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla43
Tracking Status
firefox43 --- fixed

People

(Reporter: mats, Assigned: mats)

References

(Depends on 1 open bug, Blocks 1 open bug)

Details

Attachments

(4 files, 3 obsolete files)

"12.7. Stretch Flexible Tracks"
http://dev.w3.org/csswg/css-grid/#algo-flex-tracks
"12.7.1. Find the Size of an fr"
http://dev.w3.org/csswg/css-grid/#algo-find-fr-size
The code here follows the spec text pretty close.  I noted one difference
to Chrome: the spec (and this patch) doesn't scale flex factors when
the sum is less than 1.  Chrome seems to scale them up so that all
available width is distributed (IIRC that's also what Flexbox does?).
Anyway, I think the Grid spec is clear that that shouldn't happen,
but I'll try to get confirmation on www-style on that point.

(reftests will come later, in bug 1151212)

https://treeherder.mozilla.org/#/jobs?repo=try&revision=580a48d3b619
Attachment #8625321 - Flags: review?(dholbert)
(In reply to Mats Palmgren (on vacation) (:mats) from comment #1)
> I noted one difference
> to Chrome: the spec (and this patch) doesn't scale flex factors when
> the sum is less than 1.  Chrome seems to scale them up so that all
> available width is distributed (IIRC that's also what Flexbox does?).

Flexbox is actually supposed to behave like grid here; if the flex factor sum is less than 1, then not all of the extra space will be distributed. (And the flex factors behave kind of like percents.)  I implemented this in bug 985304.

Chrome hasn't implemented this for Flexbox, though -- that's tracked here:
  https://code.google.com/p/chromium/issues/detail?id=480752

> Anyway, I think the Grid spec is clear that that shouldn't happen,
> but I'll try to get confirmation on www-style on that point.

I agree that the spec is clear on this; I think Chrome just hasn't adapted to this spec-change yet.   (Looks like the spec-change happened in Dec 2014, not too long ago:  https://hg.csswg.org/drafts/rev/d536efd568d5 )

Could you file a chrome issue on this, and CC tab?  I assume you've got a testcase with a fractional fr that shows the difference between their impl vs. what's specced. Probably worth referencing the related flexbox issue (480752, linked above) from the new bug, too.
Comment on attachment 8625321 [details] [diff] [review]
Implement "Stretch Flexible Tracks" and associated algorithms

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

Partial review notes:

::: layout/generic/nsGridContainerFrame.cpp
@@ +2087,5 @@
> +  return hypotheticalFrSize;
> +}
> +
> +float
> +nsGridContainerFrame::Tracks::FindUsedFlexFraction(

This function really returns a *length*, so it should return type "nscoord", not "float". (See also notes below on the "fr" local-variable, which should also be nscoord.)

@@ +2095,5 @@
> +  const TrackSizingFunctions& aFunctions,
> +  nscoord                     aAvailableSize) const
> +{
> +  float fr = 0;
> +  if (aAvailableSize == NS_UNCONSTRAINEDSIZE) {

It's non-obvious what the code inside this clause is trying to do, from just looking at the code.

It'd help to include a brief spec-quote here, to...
 (a) make this code more self-documenting (no need to separately open the spec just to figure out it's trying to do)
 (b) make this code still make sense if this spec-section is rewritten substantially. (If that happens -- and that seems reasonably-likely, given churn that the flexbox spec has gone through -- then I worry that it will be hard to follow this code in its current un-commented state.)

So, consider including a spec-quote from the section under "If the free space is an indefinite length" (or a paraphrased version of that spec-text) here, perhaps with its lines smeared out across the code (to the code that they correspond to) and ellipsized to show that they're all one contiguous quote?

@@ +2098,5 @@
> +  float fr = 0;
> +  if (aAvailableSize == NS_UNCONSTRAINEDSIZE) {
> +    for (uint32_t track : aFlexTracks) {
> +      float flexFactor = aFunctions.MaxSizingFor(track).GetFlexFractionValue();
> +      if (flexFactor > 0) {

IIRC, layout code mostly uses "0.0f" for 0-as-a-floating-point value. Consider using that here.

(Technically the literal value '0' is an integer, not a float. I think using the "f" suffix to make it a float is strictly more correct & may avoid some compiler warnings, though I'm not 100% sure & I don't recall the details, and maybe compilers are nicer now. Hence, leaving this up to you in case you remember the details better than I do.)

@@ +2099,5 @@
> +  if (aAvailableSize == NS_UNCONSTRAINEDSIZE) {
> +    for (uint32_t track : aFlexTracks) {
> +      float flexFactor = aFunctions.MaxSizingFor(track).GetFlexFractionValue();
> +      if (flexFactor > 0) {
> +        fr = std::max(fr, mSizes[track].mBase / flexFactor);

The variable "fr" here (and the return value of this function) are *lengths*, not floating-point values.  So fr should have type 'nscoord', and the division here should be wrapped in NS_ToCoordRound to produce a nscoord value.

@@ +2111,5 @@
> +    for (; !iter.AtEnd(); iter.Next()) {
> +      const GridItemInfo& item = aGridItems[iter.GridItemIndex()];
> +      if (item.mIsFlexing[mDimension]) {
> +        nscoord spaceToFill = MaxContentContribution(*iter, rs, rc, wm,
> +                                                     mDimension);

MaxContentContribution() involves reflow, so I want to make sure we don't call it redundantly.

Could you ensure somehow (with an assertion on some sort of flag) that we're only calling it once per grid-item + dimension? (during a given nsGridContainerFrame::Reflow call)

Right now, if an item spans multiple tracks, I think (?) this code could make us call MaxContentContribution on that item for *each of its spanned tracks* (since each track will hit this code), and that seems undesirable.  Maybe such calls could be collapsed by using a Maybe<nscoord> on GridItemInfo, to represent the max-content contribution in a particular axis? And there could be a convenience function to lazily compute the value and emplace this Maybe<>, and just directly return its contents on subsequent calls. And we only ever call MaxContentContribution via this convenience function, or something [and hence can't call it redundantly].

@@ +2125,5 @@
> +          }
> +        }
> +        float itemFr =
> +          FindFrUnitSize(range, itemFlexTracks, aFunctions, spaceToFill);
> +        fr = std::max(fr, itemFr);

FindFrUnitSize returns type 'nscoord', so itemFr should have type 'nscoord'. (As should 'fr', as I noted above)

@@ +2130,5 @@
> +      }
> +    }
> +  } else {
> +    const TranslatedLineRange range(0, mSizes.Length());
> +    fr = FindFrUnitSize(range, aFlexTracks, aFunctions, aAvailableSize);

IMO this "else" clause would be a lot clearer as an early-return, up top.

Something like:
  if (aAvailableSize != NS_UNCONSTRAINEDSIZE) {
    const TranslatedLineRange range(0, mSizes.Length());
    return FindFrUnitSize(range, aFlexTracks, aFunctions, aAvailableSize);
  }

Then you save on indentation/logical-nesting for the bulk of this function.  (This also better-matches the order of things in the spec, which is a small bonus.)

@@ +2155,5 @@
> +  if (flexTracks.Length() == 0) {
> +    return;
> +  }
> +  float fr = FindUsedFlexFraction(aState, aGridItems, flexTracks,
> +                                  aFunctions, aAvailableSize);

Here, fr should be type nscoord, too.

@@ +2161,5 @@
> +    for (uint32_t i : flexTracks) {
> +      float flexFactor = aFunctions.MaxSizingFor(i).GetFlexFractionValue();
> +      nscoord flexLength = NSToCoordRound(flexFactor * fr);
> +      nscoord& base = mSizes[i].mBase;
> +      base = std::max(base, flexLength);

I suspect we might not actually be distributing all of the space we want to distribute here (let's say, all of aAvailableSize in cases where we're distributing all-the-space), due to float error.

E.g. suppose aAvailableSize gets divided up such that "fr" is slightly too small or slightly too large, due to precision issues. Then when we distribute N copies of fr, we'll be left with N *fr being not quite equal to the total amount of space we wanted to distribute.

Making 'fr' a float doesn't help here; it just changes the scenarios under which this can happen slightly.

I think we really need some sort of "chip away at the total amount-to-be-distributed" strategy here to avoid that sort of problem. This might require reshaping the spec's algorithm a bit (since the spec assumes infinite precision).

::: layout/generic/nsGridContainerFrame.h
@@ +212,5 @@
> +  struct TranslatedLineRange : public LineRange {
> +    TranslatedLineRange(uint32_t aStart, uint32_t aEnd)
> +    {
> +      MOZ_ASSERT(aStart < aEnd && aEnd <= kTranslatedMaxLine);
> +      mStart = aStart;

Consider using an init list to set mStart / mEnd here.

@@ +256,5 @@
>    struct GridItemInfo {
> +    explicit GridItemInfo(const GridArea& aArea)
> +      : mArea(aArea)
> +    {
> +      mIsFlexing[0] = mIsFlexing[1] = false;

You should be able to use the initialization list for mIsFlexing here (which is slightly more concise). Something like:

  explicit GridItemInfo(const GridArea& aArea)
    : mArea(aArea)
    , mIsFlexing({false, false})
  {
  }

(You do something similar for mColFunctions / mRowFunctions in a different patch, I think.)
(In reply to Daniel Holbert [:dholbert] from comment #2)
> Could you file a chrome issue on this, and CC tab?  I assume you've got a
> testcase with a fractional fr that shows the difference between their impl
> vs. what's specced. Probably worth referencing the related flexbox issue
> (480752, linked above) from the new bug, too.

I filed a Chrome bug, but I couldn't figure out how to CC people on it.
https://code.google.com/p/chromium/issues/detail?id=520477
Blocks: 1194446
(In reply to Daniel Holbert [:dholbert] (out 8/5-8/10) from comment #3)
> > +float
> > +nsGridContainerFrame::Tracks::FindUsedFlexFraction(
> 
> This function really returns a *length*, so it should return type "nscoord",
> not "float".

Right, the problem is that the returned value is later muliplied with
a float and rounded in the caller so I intentionally used a floating
type here to avoid intermediary rounding errors.
I've added an explanation for the choice of return type.

> It'd help to include a brief spec-quote here, to...
>  (a) make this code more self-documenting (no need to separately open the
> spec just to figure out it's trying to do)

I honestly thought the code was fairly obvious as is, but I've
added some text from the spec as comments to help reading it.

> > +      if (flexFactor > 0) {
> 
> IIRC, layout code mostly uses "0.0f" for 0-as-a-floating-point value.

OK, sure.

> > +        nscoord spaceToFill = MaxContentContribution(*iter, rs, rc, wm,
> > +                                                     mDimension);
> 
> MaxContentContribution() involves reflow, so I want to make sure we don't
> call it redundantly.
> 
> Could you ensure somehow (with an assertion on some sort of flag) that we're
> only calling it once per grid-item + dimension? (during a given
> nsGridContainerFrame::Reflow call)

FindUsedFlexFraction is only called once(*) per dimension and it reflows
an item at most once here, so it's not that bad.  I'm aware it can
happen through other paths though, eg minmax(max-content,1fr).
(*) So far at least - bug 1174569 will change that since it may re-run
the track sizing in some edge cases, see 12.1 bullet 3 in the spec.

I'm aware this needs a solution at some point.  GetPref/MinISize
(bug 1174574) may also reflow the item.  I'm not going to tackle this
performance problem in this bug though since it's a more general problem
and it makes more sense to do it after all grid sizing code is in place.
I've filed bug 1194446.

> FindFrUnitSize returns type 'nscoord',

Actually, I've changed that to use float too for the same reason.

> IMO this "else" clause would be a lot clearer as an early-return, up top.

OK, fixed.

> > +    for (uint32_t i : flexTracks) {
> > +      float flexFactor = aFunctions.MaxSizingFor(i).GetFlexFractionValue();
> > +      nscoord flexLength = NSToCoordRound(flexFactor * fr);
> > +      nscoord& base = mSizes[i].mBase;
> > +      base = std::max(base, flexLength);
> 
> I suspect we might not actually be distributing all of the space we want to
> distribute here (let's say, all of aAvailableSize in cases where we're
> distributing all-the-space), due to float error.
> ...
> I think we really need some sort of "chip away at the total
> amount-to-be-distributed" strategy here to avoid that sort of problem. This
> might require reshaping the spec's algorithm a bit (since the spec assumes
> infinite precision).

This is a good point, but I wonder how much this matters in practice.
It only occurs with a large number of flex tracks in a small space.
I'm attaching a test that demonstrates these rounding errors.
Chrome seems to also have rounding errors for it, different from ours,
so if we want to do something about this I suggest we bring this to
the CSSWG to define the exact strategy.


> ::: layout/generic/nsGridContainerFrame.h
> Consider using an init list to set mStart / mEnd here.

'mStart' is inherited, so that wouldn't compile.

> > +      mIsFlexing[0] = mIsFlexing[1] = false;
> 
> You should be able to use the initialization list for mIsFlexing here...
>     , mIsFlexing({false, false})

error: parenthesized initialization of a member array is a GNU extension
[-Wgnu-array-member-paren-init]

> (You do something similar for mColFunctions / mRowFunctions in a different
> patch, I think.)

FYI, those are structs.
Attachment #8625321 - Attachment is obsolete: true
Attachment #8625321 - Flags: review?(dholbert)
Attachment #8647722 - Flags: review?(dholbert)
I found the proper syntax for initializing array members on stackoverflow -
just use braces, no parens.
Attachment #8647722 - Attachment is obsolete: true
Attachment #8647722 - Flags: review?(dholbert)
Attachment #8647730 - Flags: review?(dholbert)
(In reply to Mats Palmgren (:mats) from comment #6)
> > This function really returns a *length*, so it should return type "nscoord",
> > not "float".
> 
> Right, the problem is that the returned value is later muliplied with
> a float and rounded in the caller so I intentionally used a floating
> type here to avoid intermediary rounding errors.
> I've added an explanation for the choice of return type.

OK. I suppose the returned value really has units of "Length/Fr" -- and it's meant to be multiplied by a Fr value to produce a length.  This makes some sense.

I do wonder whether it'd be better, though, to structure this so that we return a "true" fraction, rather than a length/fraction hybrid. So for example, if we had two flexible tracks with sizes 1fr and 2fr, this function would return float(1/3).  And then to size a track, we multiply its own fr-value by this returned float(1/3) and multiply that by the leftover space, at the last minute, to produce the share of the leftover space. And then perhaps subtract that off of the leftover space, if we're using the "chipping away" strategy -- more on that below.


> I honestly thought the code was fairly obvious as is, but I've
> added some text from the spec as comments to help reading it.

Thanks! The comments help a lot, IMO.

> > MaxContentContribution() involves reflow, so I want to make sure we don't
> > call it redundantly.
[...]
> I'm aware this needs a solution at some point. [...]
> I've filed bug 1194446.

Thanks.

> > IMO this "else" clause would be a lot clearer as an early-return, up top.
> 
> OK, fixed.

Sorry, this went slightly differently from what I meant -- to clarify, I was thinking we should bring this short special-case up-top, as an early-return, so that the bulk of this function (FindUsedFlexFraction) can be de-indented.

So, while the bulk of this function is currently (still) inside this check...
  if (aAvailableSize == NS_UNCONSTRAINEDSIZE) 

...IMO it'd be clearer to instead start with the inverse check:
  if (aAvailableSize != NS_UNCONSTRAINEDSIZE) {

This lets you save on indentation for the bulk of this function & reduces far-reaching logic, both of which help (a little) for readability.

Not a big deal -- feel free to leave this as-is or as you originally had it, if you like.  Just wanted to clarify what I'd meant here.

> > I suspect we might not actually be distributing all of the space we want to
> > distribute here (let's say, all of aAvailableSize in cases where we're
> > distributing all-the-space), due to float error.
[...]
> This is a good point, but I wonder how much this matters in practice.
> It only occurs with a large number of flex tracks in a small space.

I do really think this is something we need to account for when implementing any "distribute $container-size between $numTracks" type of algorithm.  Otherwise, we'll be doomed to have weird edge cases where the children stomp on the parent's border, or there's a gap between the last child and the container, despite the children having been instructed to absorb all of the space.  And it's likely these edge cases can have us being off by more than a pixel, too, if the error accumulates as you add more items.

Right now, we use a "chip away at the remaining-space-to-distribute as you go" strategy for space-distribution in tables and flexbox, and it's served us well there. IMO our priorities for these sorts of algorithms should be, in this order:
 (1) We should distribute the correct amount of total space. (Particularly for commn cases where we need to distribute all of the container's space -- so we have children spanning its full size -- we shouldn't let pathological child configurations make us accidentally over- or under-deliver on this guarantee.)
 (2) We should strive to distribute space equitably (as defined by the distribution algorithm)

Right now, we're using an algorithm that prioritizes (2) at the cost of (1).  But (1) is much more important, IMO.

Goal (2) is a soft goal, since there are simply unavoidable cases where it's impossible to be 100% equitable, given a finite-resolution display device. (E.g. you just can't split 1px [or 1 app unit] between two children, or 3px between two children -- you have to favor one child or the other.)  But goal (1) *should* be always achievable, and it looks bizarre when we fail to achieve it, so I think it makes sense to prioritize it.

> Chrome seems to also have rounding errors for it, different from ours,
> so if we want to do something about this I suggest we bring this to
> the CSSWG to define the exact strategy.

Maybe? Or we should just file a Blink bug with your testcase.

If we ask the CSSWG to make a ruling on anything here, I'd think it would just be formalizing/confirming the priorities that I outlined above. Different implementations may use a different representation of a length (e.g. float vs. fixed-point), and I don't think the CSSWG wants to implicitly advocate any particular representation, or provide any particular normative spec-text that assumes a particular representation.  But I think it may be appropriate to have them confirm what should be prioritized, when we have e.g. many small items each of which take up a fraction
(In reply to Daniel Holbert [:dholbert] (vacation 8/27-9/13) from comment #9)
> OK. I suppose the returned value really has units of "Length/Fr" ...
> I do wonder whether it'd be better, though, to structure this so that we
> return a "true" fraction, rather than a length/fraction hybrid.

That's not easily done with the way the spec is written,
the "indefinite length" case in particular:
https://drafts.csswg.org/css-grid/#algo-flex-tracks

>  (1) We should distribute the correct amount of total space. (Particularly
> for commn cases where we need to distribute all of the container's space --
> so we have children spanning its full size -- we shouldn't let pathological
> child configurations make us accidentally over- or under-deliver on this
> guarantee.)
>  (2) We should strive to distribute space equitably (as defined by the
> distribution algorithm)
> 
> Right now, we're using an algorithm that prioritizes (2) at the cost of (1).
> But (1) is much more important, IMO.

I agree.  But again, that's not how the spec is written.  It'd be fairly
easy to do for the "definite length" case (when we know the target space
to fill), but I'm not sure it's even possible to implement a chip-away-
remaining-space strategy for the "indefinite length" case.  It will
certainly be an entirely different algorithm from the one in the spec,
and thus has a higher implementation, test and maintenance cost.

I definitely think that if we want that kind of algorithm then we should
ask the spec editors to rewrite the spec in such terms.  Or we should
formulate one ourselves and propose it as a replacement or at least as
a spec-blessed alternative algorithm.  I worry that if we implement our
own algorithm then it might start to diverge from the spec at some point.

Again, I do agree that such an algorithm is better, but I also feel
like it's not that important at this stage.  I'd be quite happy to ship
our Grid implementation without it and improve this at a later point.
After all, it's only a matter of rounding fidelity in some edge cases,
which I believe will be rare in practice on real web pages.

I think that we should raise this as an issue on www-style@ to see
what the editors and other implementors have to say *before* we start
implementing a different algorithm.  It might be that they had some
reason for writing it as it is?  Given that Flexbox uses a different
strategy I'm sure they are aware of the problem, so it seems a bit
odd that they chose to use a different strategy for Grid.

So, since the algorithm that I've implemented follows the spec language
pretty much exactly, I'm inclined to file this issue as a follow-up bug
for now.

Does that sound reasonable?
(In reply to Daniel Holbert [:dholbert] (vacation 8/27-9/13) from comment #9)
>   if (aAvailableSize == NS_UNCONSTRAINEDSIZE) 

OK, I swapped the logic there.

I also found a bug setting up the mIsFlexing bit.  The fix is included here,
but I'll attach it separately too so you can that change by itself.
Attachment #8647730 - Attachment is obsolete: true
Attachment #8647730 - Flags: review?(dholbert)
Attachment #8652274 - Flags: review?(dholbert)
Attached patch bug fixSplinter Review
The bug is that we assumed that HasIntrinsicButNoFlexSizingInRange returning
'false' implied we found a flex track.  That's not always the case, it also
returns 'false' when none of the spanned tracks contains an intrinsic sizing
function (or flex track).
(In reply to Mats Palmgren (:mats) from comment #10)
> (In reply to Daniel Holbert [:dholbert] (vacation 8/27-9/13) from comment #9)
> > I do wonder whether it'd be better, though, to structure this so that we
> > return a "true" fraction, rather than a length/fraction hybrid.
> 
> That's not easily done with the way the spec is written,
> the "indefinite length" case in particular:
> https://drafts.csswg.org/css-grid/#algo-flex-tracks

Ah, I see. Yeah, we'd need to separately calculate the free space to be distributed, which could be a bit tricky to separate out. (Though maybe we could just split the current return length*fraction return value into separate float (fraction) and nscoord (length) return values, in separate outparams [or as fields in a struct / Pair<>], and let the caller use or discard the length as-needed... Something like that, at least.)

> It will
> certainly be an entirely different algorithm from the one in the spec,
> and thus has a higher implementation, test and maintenance cost.

I don't think it has to be *that* different.  There would be a bit more thinking involved whenever the specced algorithm changes (but hopefully changes will be rare and/or minor at this stage).  This increased burden is worth it IMO to avoid accumulation error & bizarre gaps in our layout.

At least with flexbox, we match the spec at a high level, and the "chipping away" strategy (which is not part of the spec) just makes certain steps a bit more nuanced under the hood (e.g. we keep track of a few more quantities). It's rarely caused much of a maintenance burden.

> I definitely think that if we want that kind of algorithm then we should
> ask the spec editors to rewrite the spec in such terms.  Or we should
> formulate one ourselves and propose it as a replacement or at least as
> a spec-blessed alternative algorithm.

I don't think that's necessary - though spec-editor-feedback on our hypothetical alternative formulation would surely be useful.

fantasai has expressed to me in the past that, to the extent possible, CSS tries *not* to prescribe specific implementation strategies. Instead, they aim to set constraints (with mathematical purity / infinite precision) and describe expected results.  Sometimes the easiest way to describe the expected mathematically-pure results is with pseudocode / high-level algorithms - but that's just a guide. Then, implementations can make their own choices & compete on how best to implement these high-level algorithms (including how to handle things like rounding error), given the constraints of their own rendering engine.

So: I don't think we'd need to push for a spec change on this. Though we wouldd need to convince ourselves that our hypothetical alternative formulation is really equivalent.

> Again, I do agree that such an algorithm is better, but I also feel
> like it's not that important at this stage.  I'd be quite happy to ship
> our Grid implementation without it and improve this at a later point.

OK, I think I'm open to punting on this for now. (Though I'd strongly consider fixing it before shipping, since it's such a fundamental piece of how grid works, and I'd be uneasy about completely rewriting it after we've shipped.)

> It might be that they [the spec authors] had some
> reason for writing it as it is?

If by "as it is" you mean "not using a chipping-away strategy": see above, RE fantasai's thoughts on specs / algorithms / implementation strategies.

> Given that Flexbox uses a different
> strategy I'm sure they are aware of the problem

I think here you're suggesting that the flexbox spec *does* prescribe a chipping-away strategy?  It does not. The flexbox spec's algorithm is expressed pretty similarly to grid's. In particular: it implicitly assumes infinite precision, and it directly gives each item a fraction of the available free space [clamped to min/max sizes] & doesn't at all consider the possibility of rounding/float error.

To the extent that there are differences between the flexbox & grid spec's algoritms, I think those differences are just due to grid being more complicated with separate tracks vs. items, and being two-dimensional. (And flexbox having separate flex-shrink/flex-grow values.)

As noted above, I *implemented* flexbox using a chipping-away strategy, but that was a design choice, not something directly required by the spec.

(The flexbox spec uses a term "remaining free space", which might look like a chipping-away type quantity, but it's not -- it's just the total free space minus the flex items' base sizes & sizes of frozen items, basically. It's the free space that we can use for flexing.)

> So, since the algorithm that I've implemented follows the spec language
> pretty much exactly, I'm inclined to file this issue as a follow-up bug
> for now.
> 
> Does that sound reasonable?

I was initially leaning against it, since it means we'll have to basically rewrite a lot of this code -- but I suppose it lets us move forward and proceed with testing/improvements/etc. So I think I'm on board.
(In reply to Daniel Holbert [:dholbert] (vacation 8/27-9/13) from comment #13)
> (The flexbox spec uses a term "remaining free space", which might look like
> a chipping-away type quantity, but it's not -- it's just the total free
> space minus the flex items' base sizes & sizes of frozen items, basically.
> It's the free space that we can use for flexing.)

OK, but at least Flexbox has a "remaining free space" quantity in the spec
which lends itself to a chipping-away strategy.  For Grid we'd have to
invent it (for the "indefinte space" case) which makes me nervous about
introducing subtle differences to the spec's algorithm.

> I was initially leaning against it, since it means we'll have to basically
> rewrite a lot of this code -- but I suppose it lets us move forward and
> proceed with testing/improvements/etc. So I think I'm on board.

OK, thanks.  I think that's the best way forward.  I promise I'll take
a stab at a chip-away version before shipping (but likely not before
it's enabled in Nightly though, which I aim to do this quarter).
(In reply to Mats Palmgren (:mats) from comment #14)
> For Grid we'd have to
> invent it (for the "indefinte space" case) which makes me nervous about
> introducing subtle differences to the spec's algorithm.

True. It might be that we'd need to structure it such that the "indefinite space" scenario would use a non-chipping-away strategy (with the logic only differing in a few spots, ideally)... Or, perhaps we can reverse-engineer how much free space we're actually distributing in that scenario (inventing a new value, as you say) -- but that seems like it'd be easy to introduce error.  Anyway, needs some thought.

> OK, thanks.  I think that's the best way forward.  I promise I'll take
> a stab at a chip-away version before shipping (but likely not before
> it's enabled in Nightly though, which I aim to do this quarter).

Sounds good.

I'll take another pass at reviewing this, ignoring my float-vs.-nscoord/chip-away concerns, and hopefully have final r+ later today.
Comment on attachment 8652274 [details] [diff] [review]
Implement "Stretch Flexible Tracks" and associated algorithms

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

r=me with the following addressed as you see fit.

::: layout/generic/nsGridContainerFrame.cpp
@@ +2095,5 @@
> +  const TrackSizingFunctions& aFunctions,
> +  nscoord                     aSpaceToFill) const
> +{
> +  MOZ_ASSERT(aSpaceToFill > 0 && !aFlexTracks.IsEmpty());
> +  float flexFactorSum = 0;

float flexFactorSum = 0.0f;

@@ +2097,5 @@
> +{
> +  MOZ_ASSERT(aSpaceToFill > 0 && !aFlexTracks.IsEmpty());
> +  float flexFactorSum = 0;
> +  nscoord leftOverSpace = aSpaceToFill;
> +  for (uint32_t i = aRange.mStart, end = aRange.mEnd; i < end; ++i) {

'end' doesn't seem to add anything here, & just seems to just make things slightly more complex. (I'm used to this idiom when 'end' is being initialized to the result of a function-call, but it doesn't make sense to me when it's just copying another variable.)

Consider simplifying to just:
  for (uint32_t i = aRange.mStart; i < aRange.mEnd; ++i) {

@@ +2118,5 @@
> +    hypotheticalFrSize = leftOverSpace / std::max(flexFactorSum, 1.0f);
> +    for (uint32_t i = 0, len = flexTracks.Length(); i < len; ++i) {
> +      uint32_t track = flexTracks[i];
> +      if (track == kAutoLine) {
> +        continue; // an inflexible track

This is slightly misleading -- most inflexible tracks don't make it to this point. Only flexible-tracks-that-we-mark-as-inflexible-in-this-very-loop.

Maybe clarify as:
        continue; // Track marked as inflexible in a prev. iter of this loop.

@@ +2132,5 @@
> +        if (numFlexTracks == 0 || leftOverSpace <= 0) {
> +          return 0.0f;
> +        }
> +        restart = true;
> +        break;

Does this 'break' really make sense?  I think we should probably drop it.

Technically we're supposed to treat *all* such tracks [the tracks whose flexFactor*hypotheticalFrSize is less than their base size] as inflexible after we restart -- but this is only marking the first track, and immediately restarting.  A direct implementation of the spec would complete this "for" loop, though, I think.  I think it might produce equivalent results, but the 'break' impacts performance, and I think (?) it impacts performance poorly.

Specifically: it seems like the current version (with the "break" here) will perform badly in a case where we trivially have to freeze N consecutive tracks, let's say because they all have very small flexibilities (and the large-flexibility items are all packed at the end).  In that scenario, we'd freeze the first one; restart; walk past the first one and freeze the second; restart; walk past the first 2 and freeze the third; restart, etc. So, that ends up being O(n^2). In contrast, if we drop the 'break', we'll freeze *all* those elements up-front, in a single pass of the "for" loop, and then restart with all of those items frozen.

So I think dropping the 'break' will make us more-closely match the spec, and it improves performance, at least in this not-too-contrived example. (Maybe it hurts perf in other cases? if so, I guess we may want to keep or drop it depending on the relative likelihood/sanity of the various cases.)

@@ +2212,5 @@
> +    }
> +  }
> +  if (flexTracks.Length() == 0) {
> +    return;
> +  }

This probably wants to be flexTracks.IsEmpty().

(I think IsEmpty() is preferred over Length() == 0. The exception (IMO) is when we're about to use an array's Length() value directly -- e.g. to compute the size for an allocation -- in which case it's clearer to explicitly check Length(). But that's not the case here, so I think IsEmpty() is preferable.)

@@ +2218,5 @@
> +                                  aFunctions, aAvailableSize);
> +  if (fr != 0.0f) {
> +    for (uint32_t i : flexTracks) {
> +      float flexFactor = aFunctions.MaxSizingFor(i).GetFlexFractionValue();
> +      nscoord flexLength = NSToCoordRound(flexFactor * fr);

We need to handle the possibility that |flexFactor| and/or |fr| are infinite or NaN here (or guarantee that these values can't occur in these variables.  +inifinity seems very possible, at least; not sure about other values.)  The function mozilla::IsFinite() screens for all these values, FWIW.

Right now, we'll be exercising undefined behavior when casting these values to nscoord (which means the compiler is allowed to do literally anything).  NSToCoordRoundWithClamp might help to exclude infinite possibilities, though it doesn't help with NaN. (I'm not sure NaN is a possibility here, though, so maybe we don't need to worry about that case.)

We also need tests that exercise this code-path, and at least ensure that our behavior is predictable & we don't blow up -- it should be testable by using a value like "9999999999999999999999999999999999999999999999999999999fr" in CSS (to produce an infinite flexFactor) or approximately 1 divided by that value (to produce an infinite resolved 'fr' size, I think).

(That "999..." number is the value that we use to exercise the flexbox code for this scenario, via test_flexbox_layout.html, FWIW:
http://mxr.mozilla.org/mozilla-central/source/layout/style/test/flexbox_layout_testcases.js?rev=6625f6d27396#255
)
Attachment #8652274 - Flags: review?(dholbert) → review+
Depends on: 1201941
(In reply to Daniel Holbert [:dholbert] (vacation 8/27-9/13) from comment #16)
> float flexFactorSum = 0.0f;

Fixed.

> > +  for (uint32_t i = aRange.mStart, end = aRange.mEnd; i < end; ++i) {
> 
> 'end' doesn't seem to add anything here,

aRange is a reference so aRange.mEnd can't be put in a register.
'end' can, and very likely will, be put in a register though.

> Maybe clarify as:
>         continue; // Track marked as inflexible in a prev. iter of this loop.

Fixed.

> > +        if (numFlexTracks == 0 || leftOverSpace <= 0) {
> > +          return 0.0f;
> > +        }
> > +        restart = true;
> > +        break;
> 
> Does this 'break' really make sense?  I think we should probably drop it.

I commented it out for now with an XXX comment.
It's not needed but I figured it might be faster since if we restart
the loop we get a larger 'hypotheticalFrSize' which might eliminate
tracks earlier.

> (Maybe it hurts perf in other cases? if so, I guess we may want to keep or
> drop it depending on the relative likelihood/sanity of the various cases.)

Right, it depends on which cases we think are going to be more common.
I'll investigate that a bit more...

> > +  if (flexTracks.Length() == 0) {
> > +    return;
> > +  }
> 
> This probably wants to be flexTracks.IsEmpty().

Indeed, fixed.

> > +      nscoord flexLength = NSToCoordRound(flexFactor * fr);
> 
> We need to handle the possibility that |flexFactor| and/or |fr| are infinite
> or NaN here...

Neither can be NaN here (since we do not divide by zero on any code path).
Infinity is possible though, but I think we handle that reasonably here.

I've added some tests with extreme <flex> values.

BTW, I filed bug 1201941 on fixing the rounding errors.
https://hg.mozilla.org/mozilla-central/rev/71aea85370eb
https://hg.mozilla.org/mozilla-central/rev/52c05b4b2f46
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla43
You need to log in before you can comment on or make changes to this bug.