[css3-page][6.3.2. Margin Box Variable Dimension] Implementation difficulties

Hi,

I am in the process of implementing margin boxes from CSS3 Paged Media 
in WeasyPrint. One particular pain point is Section 6.3.2 Margin Box 
Variable Dimension Computation Rules. This section describes *what* is 
the desired behavior, but leaves the implementer with no clue as to 
*how* to do it.

For comparison, the next section on Fixed Dimension is much closer to an 
algorithm.

http://dev.w3.org/csswg/css3-page/#margin-dimension

First, has anyone implemented this and is willing/able to share the 
algorithm under an appropriate license for use in other UAs?

To give a quick overview: 3 margin boxes that share the same side are 
laid-out together in one direction. The problem can be seen as a system of:

* 0 to 9 variables (properties with a computed value of 'auto')
* 0 to 6 linear inequality constraints (lower and/or upper bounds on widths)
* 1 or 2 linear equality constraints (the total sum if fixed; the middle 
box must be centered if it "exists")
* a quadratic goal function that must be minimized (sum of squared margins)

This kind of problem is known as quadratic programming:

http://en.wikipedia.org/wiki/Quadratic_programming

General solvers exist, but they are based on iterative algorithms that 
can be slow and only give an approximate solution. Also, they’re often 
based on a whole numeric/scientific package. A big dependency for a CSS 
UA that has otherwise no need for such solvers.

Furthermore, I believe that a general solver is not required. For any 
set of input, I can tell without iterating what the output should be. 
(In other words, the algorithm could be made of conditionals, without 
loops.) I only have a hard time writing that algorithm. 9 properties 
that may or may not be auto give 2^9 = 512 cases. These can be reduced 
by symmetry but there are still a lot of cases with different behaviors, 
especially when rule 2 applies. (When the middle box exists and must be 
centered.)

Implementing CSS is generally not trivial, but I find this particular 
section especially troublesome. I’ve been at it for weeks.

Did I miss something obvious?

Regards,
-- 
Simon Sapin

Received on Tuesday, 10 January 2012 16:19:30 UTC