Re: Additional issues to address for the constraints_experiments branch?

[Elijah Newren <newren gmail com>]

On 11/14/05, Rob Adams <readams readams net> wrote:
> Things to worry about:
> Solving constraints for partial-width struts can introduce interesting
> interactions.
>
> For example, if you have something like:
>            |Strut
>            |_____
> _________  ____
> |  Strut | |Wnd|
>
> if you make the strut on the right taller so that it intersects the
> window, it will push the window over to the left, which then violates
> the other strut constraint.

Right, this one was a royal pain in the butt to figure out, and I
completely changed my method a few different times to get it right. 
:-)

> So you need to have a pretty powerful constraints solver to be able to
> handle cases like this.  The while (!satisfied) try to satisfy loop
> implements a technique called heuristic repair.  This is a search
> technique used to constraint satisfaction problems that are generally
> not too tightly constrained; that is relatively easy problems.  The idea
> is to simply move the window around so as few constraints are violated
> as possible, then iterate to try to find a feasible position.  The
> advantage of heuristic repair is that it is blazing fast, which it needs
> to be in the metacity constraint solver since it runs a lot when
> moving/resizing windows.  The disadvantage is that it's not a complete
> search algorithm, i.e. it's not guaranteed to find a solution in the
> general case.  However, given the way the constraints in metacity work,
> it will nearly always find a solution if one exists (though its possible
> that there is no solution).
>
> So I'd be interested to hear what search algorithm you use to solve the
> constraint satisfaction problem in your branch.  Iterative deepening A*
> perhaps?

Nope, it's not iterative at all.  Whenever any struts are modified, I
generate what I've called a minimal rectangle spanning set.  This set
is a list of rectangles with the property that a window will fit "on
the screen" (meaning screen minus struts) if and only if it fits
inside one of those rectangles.  While generating this list is
definitely more costly than a single iteration of your heuristic
repair, it's something I only have to generate once instead of once
every heuristic repair iteration of every meta_window_constrain[1].

The relevant function is
meta_rectangle_get_minimal_spanning_set_for_region() from boxes.c
(plus other *_region() functions) and is thoroughly tested in
testboxes.c:test_regions_okay() (and with related functionality
thoroughly tested by test_region_fitting(), test_clamping_to_region(),
test_clipping_to_region(), and test_shoving_into_region()).

Cheers,
Elijah

[1] Okay, I fibbed a little about the once thing.  I have to do it
number_xineramas + 1 times inside the update struts stuff, since that
is the number of spanning sets I generate -- one for the whole screen
plus one for each xinerama.  (I do one for each xinerama because I've
also added a constrain-to-single-xinerama constraint for
non-user-movement in order to fix Davyd's gripe about windows stupidly
positioning themselves split across xineramas).