Open frivoal opened 6 years ago
Ok, we at Igalia have been taking a look to the example.
I created a reduced one, so it's easier to check the problem: http://jsbin.com/wojujiv/1/edit?html,css,output
It has a grid container with 4 auto
columns.
And it has 3 images as grid items:
The algorithm process each of them:
Then it stays with the maximum for each column:
As you see the last 2 columns measure 200px in total, when it'll be enough if they measure 150px.
For example using grid-template-columns: 150px 150px 100px 50px
would get a more packed result.
The problem is that the algorithm is trying to fulfill some preconditions. One of them is that it doesn't want that the order of the items to result in different track sizes (so it doesn't matter the order of how items are processed the result should be the same), that's why it process all the spanning items with the same span count together. It also wants to ensure that the minimum size requirements are fulfilled. And it has also the goal to have the result as compact as possible, but first it's following the previous preconditions.
We're not sure if there'll be a better way to do this and if it'd have any consequences in more complex examples with different items order and so on.
_definition: d_x_y
is the distance between line grid x
and line grid y
_
I think the "correct" to solve this is to
d_1_2 + d_2_3 = d_1_3
d_2_3 + d_3_4 = d_2_4
d_3_4 + d_4_5 = d_3_5
d_1_2 + d_2_3 + d_3_4 = d_1_4
d_2_3 + d_3_4 + d_5_4 = d_2_5
d_1_2 + d_2_3 + d_3_4 + d_5_4 = d_1_5
d_x_y >= max( all the items between the lines x and y)
d_1_3 >= max(item_1) = max(300) = 300
d_3_5 >= max(item_2) = max(150) = 150
d_2_4 >= max(item_3) = max(150) = 250
d_first_last
.Depending on the specifics of the system, there may be one solution, or a range of solutions: your example has one degree of liberty, and can vary between 50px <= `d_1_2@ <= 200px, my example had a single solution.
I'm a long way out of school, but maybe some of the more mathematically inclined among us known the algorithms that can be used to solve that, their complexity, whether they are parallelization friendly, and whether the way we pick one solution when there is a range gives us a different choice of algorithms?
N.B.: my memory is fuzzy, but I think this is the sort of problem that can be solved by the Simplex algorithm
Actually we don't need 3 items in my example, just 2 items and 3 columns are enough to reproduce the problem. Just something like this:
<div style="display: inline-grid; border: solid thick;">
<img src="https://placehold.it/300x100" style="grid-column: 1 / 3;">
<img src="https://placehold.it/250x100" style="grid-column: 2 / 4;">
</div>
Which will cause that the columns are: 150px 150px 125px
.
When the result would be better if they were: 150px 150px 100px
.
The Working Group just discussed Can the sizing algo be made to deal with this
.
Action on Tab and fantasai to look at post-processing step suggested by fremy. Action on Florian to email Bert
I know very little about grid, but the problem in https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-379206560 looks like an LP (unless you want to consider the lengths to be an integral number of pixels, then it's ILP and much more hard).
Effectively the simplex algorithm is the common approach. The linear inequalities define a polytope which is the feasible region among which you want to find the point where the objective function is optimal. This solution may not be unique, but (if the problem is feasible) a vertex of the polytope will be one of these solutions. Simplex starts at some vertex and then keeps iterating contiguous vertices, moving in the direction of the maximum slope of the objective function. This means that in common cases, the algorithm will be fast. The downside is that a polytope has an exponential number of vertices, so the worst-case is exponential.
Instead of simplex, there are interior point algorithms which are guaranteed to be polynomial in the worst case, but they may be slower for common cases. At university I wasn't taught how these algorithms actually work so probably they are much more complex to implement than simplex, which is not difficult (as an exercise I implemented it in matlab in no more than 100 lines, I think), just a bit tricky because you want to avoid cycles and various other subtleties which can make it go wrong in edge cases.
There are solvers specialized in this kind of problems, but usually they have commercial licenses.
So yes, a post-processing step in the grid algorithm might be a better option.
I took another look at this and designed an algorithm which works in polynomial time:
col
,
max = 0
row
s.t. there is some element in (row, col)
,
col
, you associate its content width with row
.col
,
v
be the value associated with row
.max = Math.max(max, v)
col
is set to max
.row
s.t. there is a cell in (row, col)
,
max
from its associated value, clamping at zero.It doesn't respect this invariant:
it doesn't matter the order of how items are processed the result should be the same
but this wasn't either in the LP formulation above.
In particular, the result doesn't look balanced, and the size distribution varies significantly depending on whether you iterate columns left-to-right or right-to-left. But this has an easy fix: first you calculate the column sizes iterating columns left-to-right, then right-to-left, and finally you average both values per each column.
I wrote the algorithm in JS, you can see the result in
http://jsbin.com/qazuyucege/edit http://jsbin.com/juzetolazi/edit http://jsbin.com/yisedereyo/edit
The output for Florian's example is exactly like the reference (grid-template-columns: 160px 140px 110px 40px 210px
).
The output for Manuel's 1st example is a bit different (grid-template-columns: 100px 200px 75px 75px
), but close enough.
The output for Manuel's 2nd example is maybe more unexpected (grid-template-columns: 25px 275px 0px
), but the size is minimal for sure XD
So a few observations on the problem of computing intrinsic widths of columns in a table in the presence of column-spanning cells, which is a problem somewhat related to this one. (I feel like I've written this down before, but I can't find it, so I may as well write it down again.) The table case only has to deal with one set of widths at a time; I'm not sure whether that's the same for grid.
The simplest solution to the problem, and the one that gives the mathematically minimal solution, is to progressively compute the widths of each from one side of the table to the other, assigning the column the smallest width needed to accomodate all of the cells that end (in the direction the columns are being traversed) in that column. This solution is not useful because, while it gives the smallest possible table, the assignment of widths to columns is often poor. For example,
<table border>
<tr><th colspan=3>This is a long heading
<tr><td>1<td>2<td>3
</table>
produces a table that looks like:
This is a long heading | ||
---|---|---|
1 | 2 | 3 |
So in practice, the algorithm used is roughly the following (at least in Gecko since 2007 and Chromium since 2022); WebKit may differ in a few respects as described below although I haven't really tested any of this stuff since around 2007 or 2008:
Note that some implementations do not do all of these things. In particular, at least some of (Gecko pre-2007, Chromium pre-LayoutNG, WebKit, and EdgeHTML) did not do the temporary/permanent buffer setup, which leads to similarly (as above) bad distributions of widths when there are column-spanning cells whose spanned columns partially overlap. It's also possible that there may be some of those implementations that did the temporary/permanent buffer setup but didn't do the integer sort, although I don't think so (at least not in the long term). I think there were also some implementations whose distribution of the width of spanning cells may have followed rules more different from the regular table width distribution rules.
The above rules tend to strike a good balance between producing smallest-possible results and producing results with a balanced distribution of widths between columns.
We had some further discussion of this issue after the face-to-face yesterday. Part of the conclusion is that what grid already does is quite similar to the above.
After some discussion, I suggested that the result from the above algorithm could be narrowed roughly as follows:
Repeat the following until stable (I believe it will converge, but we definitely need to double-check):
Note that if you have
<div style="display: inline-grid">
<div style="width: 100px; grid-column: 1 / 3"></div>
<div style="width: 100px; grid-column: 2 / 4"></div>
<div style="width: 100px; grid-column: 1 / 4"></div>
</div>
then the current spec sizes the columns as 50px 50px 50px
.
The algorithm above considers that the items with a span of 2 have no excess (their grid area is 100px and they are 100px wide). The 3rd item has excess, but it doesn't matter because the column excess is the minimum. So it's no-op.
However, we could eliminate the excess of the 3rd item by sizing the columns as 0px 100px 0px
, as produced by my algorithm from https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-405056334.
Something that I was thinking is that https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-405056334 minimizes the total size of the table, but that's actually stronger than what was being desired here (avoiding items with unnecessary excess).
For example,
<div style="display: inline-grid; border: solid; grid-template-columns: repeat(5, auto)">
<div style="grid-column: 1 / 3; width: 100px"></div>
<div style="grid-column: 2 / 5; width: 200px"></div>
<div style="grid-column: 4 / 6; width: 100px"></div>
</div>
The current spec sizes the columns like 50px 50px 100px 50px 50px
. Then the grid is 300px wide, even though 200px would be enough with 0px 100px 0px 100px 0px
. However, no item has excess, so the current spec already behaves like this issue requests.
So, dropping the requirement of a minimal sum of track sizes, I think we could come up with al algorithm that fits much better with how the spec currently behaves.
I'm not convinced by iterative algorithms with dubious convergence that try to reduce excess after the fact. I think this needs to be handled in https://drafts.csswg.org/css-grid/#extra-space, doing something better than the "item-incurred increase" and "planned increase" thingies.
I just ran into a case that grid sizing ought to be able to deal with, but apparently cannot.
test: https://florian.rivoal.net/csswg/grid/grid-span-auto-001.html reference: https://florian.rivoal.net/csswg/grid/grid-span-auto-001-ref.html
This is grid with a few auto sized columns, and a bunch of elements spanning them in various ways. Given the size of the various things in it, it can be densely packed (as seen in the reference, with manually calculated sizes), but the current sizing algo leaves a bunch of unnecessary white space.
The motivating use case for this was trying to use grid to layout comics / manga (so it may become massively common if/when the Japanese Manga publishers starts using Grid). Since the browser has all the information it needs to calculate the "ideal" layout, grid should be able to handle that.
Finding the "correct" size doesn't seem to involve any particularly difficult math either. You cannot solve this by only resolving the (min/max) sizes of individual tracks, you also need to do the same for any pair of grid lines that items span between, but once you do that, you just have a simple system of linear equations to solve.
Now, if a grid item spans across several tracks which have different intrinsic sizing functions (like one column being max-content, and the other being min-content), I'm not 100% sure what the semantics are. But at least if all the columns it spans across have the same intrinsic sizing function, there should be no problem.