New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
frivoal opened this Issue Feb 24, 2018 · 7 comments

Comments

Projects
None yet
7 participants
@frivoal
Contributor

frivoal commented Feb 24, 2018

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.

@frivoal frivoal self-assigned this Feb 24, 2018

@frivoal frivoal added the Agenda+ F2F label Mar 6, 2018

@mrego

This comment has been minimized.

Member

mrego commented Apr 4, 2018

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.

Output of the example

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

This comment has been minimized.

Contributor

frivoal commented Apr 6, 2018

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

This comment has been minimized.

Contributor

frivoal commented Apr 6, 2018

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

@mrego

This comment has been minimized.

Member

mrego commented Apr 9, 2018

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.

Output of the last example

@css-meeting-bot

This comment has been minimized.

Member

css-meeting-bot commented Apr 10, 2018

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

This comment has been minimized.

Collaborator

Loirooriol commented Apr 11, 2018

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

This comment has been minimized.

Collaborator

Loirooriol commented Jul 14, 2018

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.

screenshot

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

screenshot

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment