Re: Additional issues to address for the constraints_experiments branch?

[Rob Adams <readams readams net>]

Ok so you take your spanning set of safe regions, then given a window
position, find the closest region that will contain your window, either
completely for placement, or partially for repairing a violated
constraint while moving/resizing?

Another interesting question: one thing that I couldn't really hack into
the constraints.c stuff when I hacked in all my other fixes was that I
really wanted the titlebar visibility constraint to only apply if there
was no contiguous region of sufficient width.  For example, in the
current code a top or bottom strut will push up a window if even one
pixel intersects the strut, but what I really wanted to do was make it
so that it would only push it up too much of the titlebar was covered,
but it was really not feasible to do it with the separate constraints
generated by each strut, since multiple struts could individually cover
parts of the titlebar.  It sounds like you'd be able to get the behavior
I wanted with your algorithm, perhaps.

Example:
______  ______
Strut| | Strut

Put a window into that tiny gap between two struts, it should get pushed
up, but make the gap wider than some minimum, and you'd be able to shove
it down there, ideally.

Another thing that I'd be concerned about with your general approach is
simply to make sure you don't end up with perhaps unnecessarily
fragmented regions.  For example, say you have an somewhat odd-sized
"safe zone" like this:
   ____   
___|  |
|     |
|_____|

There's 3 sensible ways to break this into rectangles, which your
algorithm would do, either as 3 small rectangles or as 2 rectangles in
one of 2 ways.  Regardless, it's necessary to make a choice in advance
as to how you break it up.  But its possible that, depending how you
break it up, a window could fit into the "real" region but not fit into
any of the spanning rectangles.

So if your algorithm chose:
   ____   
___|  |
|  |  |
|__|__|

or 
   ____   
___|__|
|     |
|_____|

or 
   ____   
___|__|
|  |  |
|__|__|

Your malicious adversary could make either a wider window (for the
first) or a taller window (for the second) such that it would fit into
the full region but not into 2 of those 3 possible subdivisions.

Also, I'm curious how your algorithm would behave in the case where
there exists no solution to the constraint satisfaction problem (or, as
above, your algorithm doesn't find it).  The heuristic repair technique
would iterate for a bit before finally settling on some vaguely
ill-defined "best guess" solution that will satisfy some, though not
all, constraints.  Ideally there'd be a scheme to relax certain "less
important" constraints and try again, but there isn't currently.  But
with the region-finding solution you'd probably have to worry about it a
bit more, since you probably don't want to leave the window totally
non-constrained in such cases.  Not an insurmountable problem.

-Rob "Spanner in the Works" Adams

On Mon, 2005-11-14 at 13:06 -0700, Elijah Newren wrote:
> 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).
>