Re: Additional issues to address for the constraints_experiments branch?

[Rob Adams <readams readams net>]

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.

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?

-Rob

On Mon, 2005-11-14 at 11:56 -0700, Elijah Newren wrote:
> Hi,
> 
> constraints_experiments is nearing completion and is in testable
> state.  It involves an almost total rewrite of constraints.c, plus
> lots of sanitization of things that touch it (and some other changes
> related to all the changes in constraints plus other bug fixes found
> when trying to determine whether bugs were constraints.c related or
> not...).  I've been running with it instead of HEAD for almost a month
> now, and in fact I can't stand using HEAD anymore.  ;-)  However, only
> recently did I stamp out some of the big regressions.  I'll post the
> list of bugs that have been fixed on the branch when I call for wider
> testing soon (and after I fix up the out-of-date and misleading
> documentation that I have for the branch), but first a couple
> questions:
> 
> Is anyone aware of important constraints.c issues that they'd like to
> see fixed (that don't have "constraints_experiments:targeted" in the
> status whiteboard or aren't filed in bugzilla)?  In particular:
> 
> Bill: Are there any major constraints-related accessibility problems
> other than #156699 (which should be fixed already) that you'd like me
> to look at?
> 
> Havoc, Rob: Any important points to consider/test given your
> experience with constraints stuff?  (I fixed the one thing you pointed
> out earlier, Havoc, namely the removal of the "while
> (!constraints_satisfied)  apply_constraints_again()" stuff via use of
> a much different algorithm).
> 
> Thanks,
> Elijah
> _______________________________________________
> metacity-devel-list mailing list
> metacity-devel-list gnome org
> http://mail.gnome.org/mailman/listinfo/metacity-devel-list
>