[css-grid] Can the sizing algo be made to deal with this

[frivoal]

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.

[mrego]

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 first one has 300px width and spans the first 2 columns (1st and 2nd columns).
• The second one has 150px width and spans the last 2 columns (3rd and 4th columns).
• The third one has 250px width and spans 2nd and 3rd column.

The algorithm process each of them:

• For the 1st image it sets as planned increase for 1st and 2nd column 150px.
• For the 2nd image it sets as planned increase for 3rd and 4th columns 75px.
• For the 3rd image it sets as planned increase for 2nd and 3rd column 125px.

Then it stays with the maximum for each column:

• 1st column: 150px
• 2nd column: 150px
• 3rd column: 125px
• 4th column: 75px

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.

[frivoal]

definition: d_x_y is the distance between line grid x and line grid y

---

I think the "correct" to solve this is to

1. set up the following equations that ensure the grid is a grid (gaps omitted for simplicity):

   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
   

2. for each pair of lines between which at least one item spans, set up the following inequation: 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
   

3. We try to solve that system of inequations while minimizing 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?

[frivoal]

N.B.: my memory is fuzzy, but I think this is the sort of problem that can be solved by the Simplex algorithm

[mrego]

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.

[css-meeting-bot]

The Working Group just discussed Can the sizing algo be made to deal with this.

The full IRC log of that discussion

<dael> Topic: Can the sizing algo be made to deal with this
<dael> github: https://github.com//issues/2356
<florian> https://florian.rivoal.net/csswg/grid/grid-span-auto-001-ref.html
<dael> florian: I was laying out a page of manga using grid so each cell is a grid. It should layout like ^
<florian> https://florian.rivoal.net/csswg/grid/grid-span-auto-001.html
<dael> florian: Defining a bunch of columns and rows and everything can fit, but it's manual.
<dael> florian: Here's what you get ^
<dael> florian: It has unneeded empty spaces.
<TabAtkins> Very simple example: https://github.com//issues/2356#issuecomment-379878492
<dael> florian: I think this boils down to current sizing algo not considering enough things. It's descried as a possibly improvable heuristic. If we agree this is a good thing to solve...it sounds desireable...I think this is linear programming solvable by constraints. I'm not good enough at math to put the steps but I think this is solvable.
<dael> TabAtkins: Simple example ^
<dael> TabAtkins: [explains example] We take the largest of the planned increases so we're not loosly wrapping each item. Ideal would be the latter image. It's one possible version.
<dael> florian: I believe an algo exists that we could solve it, or are we too locked into compat.
<dael> fantasai: I think we should be able to make the adjustments. I don't think anyone depends on this slight amount of slack. As time goes on we might get more constrained but I think we're not at that state. IF we could solve it it would be great, but I don't know how to do it.
<dael> florian: I might be able to research the thoroetical algo but I'm not righ to say if impl-able.
<dael> fremy: I've been working on some layouts and you can do a post-process to reduce the sizing.
<dael> TabAtkins: This example (bottom of link) it shows one possible switch. BUt there's several ways to solve it like making the column 300 and the last one goes to 0.
<dael> florian: Some examples have a range of solutions, mine has one solution.
<dael> florian: I think it's worth looking into if there's a general option that we're not blocked in. I'd appriciate a mathematically inclided person to help. Maybe do the current algo and squish would work. I
<dael> fremy: browsers are impl grid and we don't want to change whole algo so that's easier.
<dael> TabAtkins: And your site may be doing it for you. In the manga example your images have known widths, it's just easier if CSS does it for you.
<dael> fantasai: TabAtkins and I can take an action to look at post-processing step to see if that works. Maybe send a email to bert with a link to this issue to see if he has some insight.
<dael> ChrisL: We was talking to people from Monash (sp?) univeristy with expertese.
<TabAtkins> s/making the column 300 and the last one goes to 0/making the columns 50,250,0, which is a big change from the current way they lay out/
<dael> fantasai: We also had Caesar (sp?) who was working on an impl of Bert's grid spec.
<ChrisL> s/(sp?)//
<fantasai> s/Caesar/César/
<Rossen> dael, here's the illustration that should go with the BFC discussion (issue 2452) https://lists.w3.org/Archives/Public/www-archive/2018Apr/0001.html
<ChrisL> s/Monash (sp?)/Monash/
<dael> florian: I think the trickier part is that this is more complicated. If we have auto sizing it's simplier. If you have one min and one max you span. It's much harder to explain to people that don't know CSS but I'll try.
<dael> astearns: Anything more?
<dael> florian: Nope.

Action on Tab and fantasai to look at post-processing step suggested by fremy.
Action on Florian to email Bert

[Loirooriol]

I know very little about grid, but the problem in #2356 (comment) 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.

[Loirooriol]

I took another look at this and designed an algorithm which works in polynomial time:

1. For each column col,
   1. Let max = 0
   2. For each row row s.t. there is some element in (row, col),
      1. For simplicity I assumed there can only be a single element in that cell (no overlapping), but shouldn't be hard to generalize.
      2. If an element starts at the beginning of col, you associate its content width with row.
      3. If an element ends at the end of col,
         1. Let v be the value associated with row.
         2. Set max = Math.max(max, v)
   3. The width of the column col is set to max.
   4. For each row row s.t. there is a cell in (row, col),
      1. Subtract 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

Code

window.addEventListener("load", function() {
  document.querySelectorAll(".polyfill").forEach(polyfill);
});

function polyfill(grid) {
  grid.style.display = "block";
  let itemData = new Map();
  let n = 0;
  let m = 0;
  for (let child of grid.children) {
    let cs = getComputedStyle(child);
    itemData.set(child, {
      colStart: cs.gridColumnStart - 1,
      colEnd: cs.gridColumnEnd - 1,
      rowStart: cs.gridRowStart - 1,
      rowEnd: cs.gridRowEnd - 1,
      contentSize: child.offsetWidth,
    });
    n = Math.max(n, cs.gridRowEnd - 1);
    m = Math.max(m, cs.gridColumnEnd - 1);
  }
  grid.style.display = "";
  let gap = parseFloat(getComputedStyle(grid).columnGap) || 0;
  let cells = Array(n).fill().map(_ => Array(m));
  for (let data of itemData.values()) {
    let {rowStart, rowEnd, colStart, colEnd} = data;
    for (let i = rowStart; i < rowEnd; ++i) {
      for (let j = colStart; j < colEnd; ++j) {
        cells[i][j] = data;
      }
    }
  }
  function main(reversed) {
    let columnSizes = Array(m);
    let currentSizes = Array(n);
    let col = reversed ? m - 1 : 0;
    while (reversed ? col >= 0 : col < m) {
      let max = 0;
      let rowsWithCells = [];
      for (let row = 0; row < n; ++row) {
        let cell = cells[row][col];
        if (!cell) continue;
        let {colStart, colEnd} = cell;
        if (reversed) [colStart, colEnd] = [colEnd-1, colStart+1];
        rowsWithCells.push(row);
        if (colStart === col) {
          currentSizes[row] = cell.contentSize;
        }
        if (colEnd - 1 === col) {
          max = Math.max(max, currentSizes[row]);
        } else {
          currentSizes[row] = Math.max(0, currentSizes[row] - gap);
        }
      }
      columnSizes[col] = max;
      for (let row of rowsWithCells) {
        currentSizes[row] = Math.max(0, currentSizes[row] - max);
      }
      col += reversed ? -1 : 1;
    }
    return columnSizes;
  }
  let columnSizes1 = main(false);
  let columnSizes2 = main(true);
  let average = columnSizes1.map((n, i) => (n + columnSizes2[i])/2);
  let result = average.map(n => n + "px").join(" ");
  grid.style.gridTemplateColumns = result;
  let pre = document.createElement("pre");
  pre.textContent = "columns: " + result;
  grid.parentElement.insertBefore(pre, grid.nextSibling);
}

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

[dbaron]

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:

1. for each column, maintain two copies of the intrinsic width that we're computing (note that we may compute min-content and max-content and percentage widths at the same time, but each one requires holding two values): the permanent value and the temporary value.
2. Initially, take all the non-column-spanning cells, and store the width needed for the largest cell in the column in the permanent value for its column. (Note that there's some interaction between the max-content and percentage values that I'll ignore here since it's not relevant.)
3. Then, for each value of column-span that exists in the table, in increasing order (2, 3, 4, etc.):
   1. Examine all the cells with that column-span value, and for each such cell, if the sum of the values already allocated to the permanent width values of the columns that it spans is not sufficient to hold the width needed by the cell, distribute that excess to the columns according to roughly the same width distribution algorithm that is used to distribute excess table width to the cells, and increase the temporary value for the column to be at least that column's portion of the excess
   2. Add each column's temporary value to the permanent value, and set the temporary value back to zero for the next iteration of the loop over column-span numbers. This separation of the temporary and permanent values means that the order that the column-spanning cells are traversed doesn't affect the layout, since no cell with colspan N affects the widths distributed by a different cell that also has colspan N or smaller, but it affects the widths distributed by all cells that have colspan larger than N.

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.

[dbaron]

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):

1. For each column in the grid/table, examine all cells that are part of the column (i.e., their span includes the column) and compute the smallest excess for all such cells, where the excess of a cell is the sum of the widths assigned to all columns it spans minus the width needed by the cell
2. For each cell in the table whose column has nonzero excess, compute the potential overflow, as the width needed by the cell minus the sum of the widths assign to all columns its spans, plus the excess assigned to each such column. If this value is greater than zero, then follow the rules for distributing that value as width among the cell's columns, and for each column ensure that the excess reduction value for the column is at least that amount distributed.
3. For each column, subtract (excess - excess reduction) from the width. (Or does it make sense to do this by colspan number iterations rather than in a single loop?)

[Loirooriol]

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 #2356 (comment).

[Loirooriol]

Something that I was thinking is that #2356 (comment) 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.