Gecko:Column Balancing

From MozillaWiki
Jump to: navigation, search

Suppose you have a block of text that needs to be split into three columns, and the width is known but the height is not. We want to choose a height so that the text is evenly divided across the columns. This is the problem of "column balancing".

We need an algorithm for doing this that is fast, incremental, produces pleasing results, and is not difficult to implement in the Gecko architecture.

Here's Gecko:Roc's proposal: let's say a height H is 'feasible' if reflowing the columns with H as the available height produces no overflowing content --- everything fits. Our algorithm will find an H such that H is feasible but H-1 is not feasible; let's call such an H 'acceptable'. It will *not* guarantee that all H' < H are infeasible --- that's too hard.

Here's an algorithm to do that. On an initial reflow, we set H to be NS_INSTRINSICSIZE (unconstrained) and reflow the content. This gives us a feasible initial height --- the height of the content all flowed into one column. We guess H to be the feasible initial height divided by the number of columns.

Then, and for all non-initial reflows, we start with the current value of H and find a new value H' that is acceptable. There are two steps: first test if H is acceptable, then if it is not, change H to a new guess and repeat.

[[[Gecko:Roc]]] This was part of my old proposal but it is NOT what I ended up implementing.

To test if H is acceptable, we reflow with height H-1, and then again with height H. H is acceptable if the first reflow had leftover content but the second reflow did not.

Making a new guess depends on why H is not acceptable. If H-1 is feasible then we set H to H-1 for the next guess. If H is not feasible then we set H to H+1, unless this is the first guess for a non-initial reflow, in which case we set H to the sum of the heights of the columns divided by the number of columns (this is to handle large content appends coming from the parser).

We can skip some of these reflows by optimizing feasibility tests, by recording for each column block its sensitivity to changes in available height. Each column block will be able to return an interval around the last available-height it was reflowed with, such that all available-heights in the interval would give exactly the same reflow result. For example, a block of 20 lines of 10px each, reflowed with available-height 95px, would return an interval [90px, 100px). Then, if we have reflowed with some available height H, and we want to reflow with another height H', then we can skip reflowing any column whose insensitivity interval includes H'. (Note that a column may need to be reflowed anyway if its predecessor column pushed lines into it.) In particular instead of increeasing or decreasing H by one layout unit at a time, we will be able to skip directly to the next height value that can make a difference to the layout.

The reflows issued to search for H values will be resize reflows, since the available height is the only thing changing.

A thought from dbaron: If we had a constrained height reflow mechanism where the constraint was a minimum rather than a maximum, would this be easier? That would allow us to use the (full height / number of columns) but ensure we don't overflow.

[[[Gecko:Roc]]] I don't see how that would work. Wouldn't it mean that all the error was pushed to the last column, making it much too short or much too long? That probably wouldn't look good. Plus it would complicate things to have frames supporting both minimum and maximum height constraints, and require a bunch of extra code to be written.

[[[Gecko:Roc]]] Here's an example to think about:

Big-Image: Suppose all widths are fixed and all lines are 10px high. Suppose we have 9 lines, followed by a 100px image, followed by another 9 lines. Here's what we should get, I believe:

  • 2 columns -> 9 lines + image | 9 lines (i.e., favour making the first column taller)
  • 3 columns -> 9 lines | image | 9 lines (i.e., don't require the first column to be the tallest, if you can minimize the height some other way)
  • 4+ columns -> 9 lines | image | 9 lines (i.e., once we've chosen the balance height, we just fill blindly from left to right, we don't try to balance a subset of the columns)

I believe that with a minimum available height constraint, the 3-column case would become 9 lines + image | 9 lines, which isn't so great. Also, with the minimum available height constraint suggests that either 1) you take the computed height of the frame as the minimum available height constraint, which seems wrong or 2) you calculate the computed height of the frame as the max of the column heights afterward, which leaves you in the unfortunate situation where the layout is not the same as if you'd explicitly set the height to the same value.