After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 86682 - Supplement WM spec to allow partial-width panel struts
Supplement WM spec to allow partial-width panel struts
Status: RESOLVED FIXED
Product: metacity
Classification: Other
Component: EWMH specification
unspecified
Other Linux
: High minor
: GNOME2.x
Assigned To: Metacity maintainers list
Metacity maintainers list
AES[BADBUG]
: 81777 83647 88755 88807 90368 91887 92923 101211 104813 105417 107091 107281 111681 112268 114011 115937 118819 120169 125851 (view as bug list)
Depends on:
Blocks: 108152 108497
 
 
Reported: 2002-06-28 04:19 UTC by vaino.jarvela
Modified: 2004-12-22 21:47 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
patch against CVS head to fix the "phantom panel" problem for xinerama (4.56 KB, patch)
2003-02-23 19:10 UTC, Rob Adams
none Details | Review
Fixed patch that doesn't contain extra garbage. (3.76 KB, patch)
2003-02-23 19:16 UTC, Rob Adams
none Details | Review
updated patch for new constraints code (4.25 KB, patch)
2003-03-11 20:53 UTC, Rob Adams
none Details | Review
_NET_WM_STRUT_PARTIAL (39.15 KB, patch)
2003-06-07 21:31 UTC, Rob Adams
none Details | Review
updated patch (52.03 KB, patch)
2003-06-09 02:17 UTC, Rob Adams
none Details | Review
and here's the latest patch. (52.36 KB, patch)
2003-06-09 04:15 UTC, Rob Adams
none Details | Review
latest patch (55.24 KB, patch)
2003-06-11 03:20 UTC, Rob Adams
none Details | Review
use requested rect instead of orig rect (59.51 KB, patch)
2003-06-11 17:11 UTC, Rob Adams
none Details | Review
updated for current CVS. Let's set a record for most revisions of one patch on a bug. (55.99 KB, patch)
2003-06-12 07:36 UTC, Rob Adams
none Details | Review

Description vaino.jarvela 2002-06-28 04:19:34 UTC
I'm using Geforce4 nview/twinview multiview-support(it has Xinerama support
with it).

One, the panels won't stretch to the other monitor. This is something more
related to Gnome, but isn't really a big problem at all. Maybe even better
that it doesn't.

Two, windows still think that the panels are there and when i maximize they
leave spaces where the panels would be. This doesn't happen with Sawfish.
Comment 1 Luis Villa 2002-07-30 01:33:23 UTC
Any thoughts on this one, Mark?
Comment 2 Mark McLoughlin 2002-07-30 02:41:17 UTC
Both of these are actually the expected behaviour. We want the panel
to not stretch across both screens (it actually takes quite a bit of
implementation to do it that way), but it still must reservere a strut
all the way across the screen, and that's what metacity uses to figure
out how much space a maximised window can take up ....


I would close as WONTFIX or NOTABUG, but I'd prefer Havoc to look at
it first ...
Comment 3 Havoc Pennington 2002-07-30 19:39:17 UTC
A spec bug, we need the spec to support a partial-width strut.

A not-that-terrible hack would assume that struts only apply to the
current xinerama, but that would technically break the spec.
Comment 4 Mark McLoughlin 2002-07-30 20:30:45 UTC
Would be useful for corner and sliding panels too ...
Comment 5 Havoc Pennington 2002-08-10 01:28:09 UTC
*** Bug 90368 has been marked as a duplicate of this bug. ***
Comment 6 Havoc Pennington 2002-08-10 17:10:10 UTC
*** Bug 88807 has been marked as a duplicate of this bug. ***
Comment 7 Havoc Pennington 2002-08-10 17:10:43 UTC
*** Bug 88755 has been marked as a duplicate of this bug. ***
Comment 8 Havoc Pennington 2002-08-10 17:11:01 UTC
This Red Hat bug is a dup, remember to close it too:
https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=69203
Comment 9 Havoc Pennington 2002-08-10 20:25:54 UTC
This bug should cover both Xinerama case, and corner/sliding panel case.
Comment 10 Havoc Pennington 2002-08-10 20:26:41 UTC
*** Bug 83647 has been marked as a duplicate of this bug. ***
Comment 11 Havoc Pennington 2002-08-10 20:27:24 UTC
*** Bug 81777 has been marked as a duplicate of this bug. ***
Comment 12 Mark McLoughlin 2002-09-10 08:21:29 UTC
*** Bug 91887 has been marked as a duplicate of this bug. ***
Comment 13 Mark McLoughlin 2002-09-11 02:40:24 UTC
*** Bug 92923 has been marked as a duplicate of this bug. ***
Comment 14 Havoc Pennington 2002-09-11 03:18:37 UTC
The kind of pesky thing I've been thinking about here is that 
you probably (?) want maximize to avoid the corner panels, but 
don't want moving windows to avoid them... or maybe corner panels
should just be on the bottom instead of the top, and not set any strut
at all?
Comment 15 Havoc Pennington 2002-09-24 18:26:12 UTC
There's been some more wm-spec-list discussion recently.

We need to get this nailed down for 2.2.
Comment 16 shandy 2002-12-14 21:58:14 UTC
*** Bug 101211 has been marked as a duplicate of this bug. ***
Comment 17 Rob Adams 2003-01-04 19:55:37 UTC
Ping.

This is a major UI problem for those running multiple heads.  I would
like to see some progress on this issue.  Maybe a simple temporary
hack to tide us over in the meantime is in order?

Also, it's possible to move the panel to the space between the heads
-- i.e. along the edge between the displays.  This causes horrible
things to happen with the window manager. (this I would propose fixing
by disallowing panels on internal edges, but that's a gnome-panel bug).

-Rob
Comment 18 Havoc Pennington 2003-01-04 20:23:46 UTC
There was some discussion on wm-spec-list

I would say we should just make struts apply only to the xinerama
heads overlapping the window that sets the strut.

Panels being allowed "in the middle" is a gnome-panel issue.

Comment 19 Peter S Russell 2003-01-10 03:13:09 UTC
Is this bug what stops me from placing windows at the same height as a
corner panel?  If so I think that it should be made a priority.

If a window cannot be placed next to a corner panel then there is no
point in being able to have corner panels, you use up just as much
screen as if it was a full length panel.
Comment 20 Mark McLoughlin 2003-01-10 03:27:13 UTC
Yes, I agree ... AFAIR, though, Havoc didn't think that partial width
struts were useful in general - just in the case of xinerama ..

Havoc: I think you were suggesting that panels that don't take up the
full screen(monitor) width don't set a strut at all - is that right ? 
Comment 21 Havoc Pennington 2003-01-10 03:51:07 UTC
I think there are several options, corner panels could either:

 - not set a strut and be below normal windows in stacking order

or 

 - set a partial-widget strut

or
 
 - something else

But you have to consider a) window titlebars should not end up
entirely underneath a panel, metacity should prevent that 
b) maximization should not stick the window under a panel
c) you should be able to move a window into empty space *next to* a
corner panel.
Comment 22 Peter S Russell 2003-01-10 14:34:52 UTC
I think a large part of the problem is the design of panels
themselves.  Depending on how a user uses panels different behaviours
make sense.

Applets should always remain visible, otherwise they are useless. 
However launchers are used less frequently, and it wouldn't be the end
of the world if a window is maximised over them, since when a user has
a window maximised they presumably are working solely inside that
window, and don't need to launch other programs.  

I've always thought that having applets and launchers in the same
panel without any sort of seperator was a big UI mistake, and I
personally use two, one at the top which autohides for launchers, and
another at the bottom for applets that doesn't.

I really don't know what the best behaviour for maximise is, I'm
personally the sort of user that likes to have several windows visible
at once.  I don't think I've used a maximise button in as long as I've
been using linux, and I think that it another UI mistake.  Its a hang
over from opperating systems like Windows which couldn't deal with
propper multi-tasking and were designed to be used at lower
resolutions, so encouraged more of a task-switching approach.
Comment 23 Havoc Pennington 2003-01-20 03:13:33 UTC
See also the thread at
http://mail.gnome.org/archives/wm-spec-list/2002-September/msg00011.html
Comment 24 Rob Adams 2003-02-23 19:10:01 UTC
OK most of the code is now in metacity to handle, at least, partial
width-style struts for xinerama, though not for the corner panel case.

See Bug 95014 for discussion of the per-xinerama work areas that make
this possible.  

I'm attaching a patch that fixes the "phantom panel" problem for
current CVS, just so we have it convenient somewhere.  This
essentially is the stuff in my patch for Bug 95014 that hasn't gone in
yet.

We'll want to discuss an ultimate solution for how we want to handle
the corner panel case as well as this case.  I think that the simplest
solution would be to not have corner panels, but people aren't going
to like that :-).

Here are my thoughts:  I think the best option is a partial-width
strut hint.  We implement this by treating partial width struts as
full-width struts for computing the work area (the region "in between
the struts" used for all constraints right now).  However, we would
implement also a "move region" in addition to the work area that would
ignore partial-width struts completely.  Then we can add constraint
code that prevents windows from moving/resizing so that they overlap
windows that set partial-width struts.  This is sort of like the
concept of avoided windows in sawfish.

I'm sort of wondering at this point why we need struts at all. 
Wouldn't an avoid hint have been easier?
Comment 25 Rob Adams 2003-02-23 19:10:53 UTC
Created attachment 14550 [details] [review]
patch against CVS head to fix the "phantom panel" problem for xinerama
Comment 26 Rob Adams 2003-02-23 19:16:24 UTC
Created attachment 14551 [details] [review]
Fixed patch that doesn't contain extra garbage.
Comment 27 Havoc Pennington 2003-02-23 19:40:10 UTC
The reason we didn't use an avoid hint is autohide panels (they don't
set a strut at all, or only set a strut for the hidden size).
Comment 28 Rob Adams 2003-02-23 21:08:21 UTC
Should we up the priority on this bug?  This seems like something that
really needs to be in the next version of GNOME.
Comment 29 Havoc Pennington 2003-02-23 23:09:01 UTC
"GNOME2.x" milestone indicates that in theory, but marking high since
there's a patch and lots of dups.
Comment 30 Havoc Pennington 2003-02-25 22:36:51 UTC
*** Bug 104813 has been marked as a duplicate of this bug. ***
Comment 31 Havoc Pennington 2003-02-25 22:57:19 UTC
*** Bug 105417 has been marked as a duplicate of this bug. ***
Comment 32 Havoc Pennington 2003-02-26 02:50:37 UTC
*** Bug 107091 has been marked as a duplicate of this bug. ***
Comment 33 Mark McLoughlin 2003-03-01 01:34:48 UTC
*** Bug 107281 has been marked as a duplicate of this bug. ***
Comment 34 Rob Adams 2003-03-11 20:38:22 UTC
There doesn't seem to be any progress on this issue in terms of
wm-spec or anything.

I think we should commit the rest of the patch to fix the phantom
panels for xinerama.
Comment 35 Rob Adams 2003-03-11 20:53:39 UTC
Created attachment 14930 [details] [review]
updated patch for new constraints code
Comment 36 Rob Adams 2003-03-11 20:56:35 UTC
Havoc made the comment in the changelog that you added the
all_xineramas work_areas function back in.  This patch disables the
only use of the all_xineramas work_area function since it's not ideal
unless all the work areas are the same.  Which they are until you
apply this patch :-)  We can probably go ahead and rip that function
back out though.

-Rob
Comment 37 Havoc Pennington 2003-03-11 21:00:11 UTC
I'm not a big fan of committing a patch unless it at least represents
a solid proposal for wm-spec-list that addresses all the issues. 
And if we have such a proposal, we may as well propose it on wm-spec-list.
Comment 38 Rob Adams 2003-03-12 02:13:26 UTC
I think that it's exceedingly likely that the code for computing
per-xinerama work areas as it stands is correct for whatever is
eventually decided.

The corner panel case will probably end up taking the form of some
sort of move constraint hacking.  I have some ideas about how to
handle that; I'll hack something together eventually.

But in the meantime, I don't really see any reason why we shouldn't at
least commit the partial fix.  And I haven't been impressed so far at
the expreme responsiveness of the wm-spec-list.
Comment 39 Rob Adams 2003-03-12 02:34:31 UTC
at the very least though, we should sort out the constraints code
before trying to do this.
Comment 40 Havoc Pennington 2003-04-27 07:11:41 UTC
*** Bug 111681 has been marked as a duplicate of this bug. ***
Comment 41 Rob Adams 2003-04-27 07:15:47 UTC
I'll try to get around to writing the partial-width strut patch in
probably another month or so.  Been really busy lately, and that patch
will be a bitch to write.
Comment 42 Havoc Pennington 2003-04-27 07:19:52 UTC
Link to latest discussion:
http://mail.gnome.org/archives/wm-spec-list/2003-March/msg00003.html
Comment 43 Andrew Sobala 2003-04-27 09:31:32 UTC
We should really have this in GNOME 2.4 for multihead to work properly
Comment 44 Rob Adams 2003-05-05 15:27:27 UTC
*** Bug 112268 has been marked as a duplicate of this bug. ***
Comment 45 Kjartan Maraas 2003-05-11 15:36:58 UTC
Is this backportable to 2.2.x too?
Comment 46 Rob Adams 2003-05-11 16:08:44 UTC
no, it will be essentially impossible to backport this without
bringing in essentially all of the changes in the unstable branch.
Comment 47 Mark McLoughlin 2003-05-30 08:47:23 UTC
*** Bug 114011 has been marked as a duplicate of this bug. ***
Comment 48 Rob Adams 2003-06-07 21:31:13 UTC
OK I have what I think is the Definitive Solution (TM).  The patch to
be attached implements the new property 

_NET_WM_STRUT_PARTIAL which is a 12-item cardinal using the values (in
order):
left_strut, right_strut, top_strut, bottom_strut, left_start_y,
left_end_y, right_start_y, right_end_y, top_start_x, top_end_x,
bottom_start_x, bottom_end_y

Metacity will ignore any _NET_WM_STRUT if this property exists, so
that applications can feel free to set both properties for backwards
compatibility.  In the new EWMH, the _NEW_WM_STRUT property will be
deprecated.

Most of the real work is done in get_outermost_onscreen_positions
which will go through a cached list of struts for each of the four
sides to determine where the window is allowed to go.  Maximized
windows are now handled as a special case in update_position_limits
because regular windows will only have titlebar constraints with
regard to partial width struts.

This patch handles both the xinerama and arbitrarily aligned corner
panel/partial-width edge panel completely.  I will post to
wm-spec-list my patch to the WM spec and post a link here once I've
done that.
Comment 49 Rob Adams 2003-06-07 21:31:43 UTC
Created attachment 17290 [details] [review]
_NET_WM_STRUT_PARTIAL
Comment 50 Rob Adams 2003-06-07 21:56:05 UTC
Here's the wm-spec-list thread:
http://mail.gnome.org/archives/wm-spec-list/2003-June/msg00002.html

By the way, the above patch also patches metacity_window_demo to use
partial-width dock windows so that this can be tested easily.

A gnome panel patch still needs to be written, but hopefully someone
else is willing to do that since I still run Gnome 2.2 except for
metacity and gnome-panel now has Gnome 2.3 dependencies.  It should be
a very easy patch to write.
Comment 51 Havoc Pennington 2003-06-08 17:27:17 UTC
Thanks a lot, comments:

Substantive:

- it seems to me there's a major conceptual problem in 
  get_outermost_onscreen_positions(). Aren't you using the 
  window's *current* position to decide which struts apply?
  But the current position may not have anything to do with 
  where the window ends up...

- meta_window_new() should probably initialize the new 
  strut rectangle fields, unless I'm missing something

- with the 4 strut rects taking up sizeof(int) * 16 bytes per window,
  and most windows not having struts, I can imagine it being
  worthwhile to do MetaStruts containing the struts and have
  MetaWindow contain MetaStruts* which is NULL if a window has no
  struts. Could also get rid of window->has_struts if doing 
  this and just use window->struts != NULL

- should probably do some strut sanity checking when reading the
  property; does metacity get hosed if someone sets negative or 
  huge struts?

- let's just blow away the old WIN_HINTS_DO_NOT_COVER crap, 
  nobody is running metacity with GNOME 1.4 anymore

Nitpicks:

- it'd be nice to add the new atom to the end of the list
  instead of in the middle, if only to simplify backports 
  between metacity branches

- +  GList *workspaces = meta_window_get_workspaces (window);
  +  GList *tmp = workspaces;

  I'd declare and init the variables separately

- s/MIN(/MIN (/ s/MAX(/MAX (/

- args to meta_rectangle_equal should be "const MetaRectangle*"
  (though I probably messed this up elsewhere)

Comment 52 Rob Adams 2003-06-08 18:11:03 UTC
Yea that current thing bothered me too.  If the window ends up being
contrained on multiple axes it's possible that one of the contraints
could slip past.  The only way I can think of though to fix this is to
iterate to a fixed point (which would, I think, be guaranteed to
happen after two runs through the onscreen constraints).  So maybe we
should just do it that way: run through the constraints twice.  If we
were to do that, we should note that what we're doing in effect is
finding a feasible solution along the boundary of the solution-space
simplex.  In other words, it becomes a constraint solver.

And 15 extra words/window?  You're kidding right?  So after 8738
no-strut windows on the display, we'll use up almost an extra
megabyte.  On the other hand, if we have 131072 window _with_ struts
on the display, having a separate data structure will use up an extra
megabyte :-)

But all kidding aside, if you really want to do it that way I'll go
ahead and code it.  Makes the code a tiny bit uglier, but not too bad.

I didn't think it was necessary to initialize the strut rects since
they will never be used unless window->has_struts and they are
initialized anyway when window->has_struts becomes true.  Plus I got
really, really sick of typing window->left_strut.x
window->left_strut.y etc ad nauseum :-).

Negative or huge struts: If the strut is negative, it will have no
effect, since the regular window edge constraint will take precedence.
 If the strut is huge, I would say that the correct behavior is to be
completely hosed.  One of the wm-spec-list posts semi-addressed this
in the context of internal-edge struts.  We could do something like
enforce that struts can't be more that say half the total screen area.
Comment 53 Rob Adams 2003-06-09 02:17:41 UTC
Created attachment 17339 [details] [review]
updated patch
Comment 54 Rob Adams 2003-06-09 02:26:40 UTC
updated patch rips out WIN_HINTS stuff, and adds the MetaStrut technique
(window->left_strut is now window->struts->left if window->struts).

Also updates the constraints code to be a bit more conservative on
deciding when a strut should apply to ensure that there is no way that
a window titlebar could get stuck behind a strut or some set of struts.

Also changes the TITLEBAR_ONSCREEN value from 36 to 75, since I found
that in practice 36 wasn't enough to me able to get at the window
title bar when it's pushed all the way to the left.  We should really
do some sort of calculation on the theme (or perhaps make it part of
the theme?) to determine what it should be, but 75 seems like a good
number for now.

I've tried very hard to construct a situation under which this code
fails to work, and been unable to.  The key here is that for some
reason that I don't completely understand, the contraints stuff get
called multiple times, so all that stuff I mentioned earlier about the
window converging to a fixed point in two iterations is happening
exactly as I was saying.

The weird part is that I can't figure out why in the heck the window
gets the constraints applied twice under certain circumstances. 
Here's an example:
Run the patched metacity-window-demo.  Start a top strut.  The
position of this dock is carefully chosen.  Move a window into the top
left corner as far offscreen as you can.  Now start a left strut. 
This strut will push the window to the right.  When that happens, it
is now into the region affected by the top strut.  On the second pass,
the top strut pushes it down into the correct, accessible position.
Comment 55 Rob Adams 2003-06-09 04:13:42 UTC
Here's the ChangeLog for the latest patch, which should be helpful:

2003-06-09  Rob Adams  <robadams@ucla.edu>

	Update constraints code to support the new _NET_WM_STRUT_PARTIAL
	EWMH draft specification.  See #86682.  Also, fix a bug involving
	work area invalidation on metacity startup.  Fix for #108497.
	Finally, some minor fixes for full screen windows.

	* src/window.h: Add new MetaStruts structure to store strut rects
	for a window.  Remove has_struts and do_not_cover flag, and
	support new MetaStruts instead of the four ints.
	
	* src/window.c (meta_window_new): change initialization to work
	with new struts.  Also, move meta_window_update_struts call to
	after the workspaces are initialized to fix #108497.  Remove
	do_not_cover and related code.
	(move_resize_cmp): remove function since no longer needed, as
	metacity does not support do_not_cover any more.
	(idle_move_resize): don't bother sorting the windows; it doesn't
	matter any more.
	(meta_window_client_message): remove win_hints code
	(process_property_notify): add strut_partial
	(update_struts): change function name to meta_window_update_struts
	and expose in external MetaWindow API.  Support partial width
	struts and the new strut rects.
	(recalc_do_not_cover_struts): remove function no longer needed

	* src/workspace.h: add new GSLists containing pointers to all
	relevant struts for this workspace.

	* src/workspace.c (meta_workspace_new): initialize the list of
	strut rects for this workspace.
	(meta_workspace_free): free the strut rect lists
	(ensure_work_areas_validated): support new struts and new strut
	rect lists.  Unleash the per-xinerama work areas.

	* src/constraints.c (get_outermost_onscreen_positions): Use the
	current window position along with the new per-workspace strut
	rects to compute the constraints that apply to a particular
	window.
	(constraint_hint_applies_func): don't do hints constraints on
	fullscreen windows
	(update_position_limits): for maximized windows use the work areas
	to set the position limits; for other windows rely on the struts
	constraints to be computed later in
	get_outermost_onscreen_positions
	(meta_window_constrain): don't apply aspect ratio hints to full
	screen windows

	* src/display.c (meta_display_open): remove _WIN_HINTS atom and
	add _NET_WM_STRUT_PARTIAL
	(meta_rectangle_equal): new helper function for MetaRectangles

	* src/display.h: remove atom_win_hints and add
	atom_net_wm_strut_partial, and add meta_rectangle_equal.

	* src/screen.c (meta_screen_rect_intersects_xinerama): change
	_window_intersects_ to _rect_intersects_ which is more useful now.
	(meta_screen_resize_func): update struts on windows with struts
	since struts are relative to the screen size, and this function is
	called when the screen size updates.

	* src/screen.h (meta_screen_rect_intersects_xinerama): change
	_window_intersects_ to _rect_intersects_ which is more useful now.

	* src/window-props.c (meta_display_init_window_prop_hooks): add
	hook for strut_partial; remove it for win_hints

	* src/tools/metacity-window-demo.c: Support partial-width struts
	on the dock window tests for metacity testing purposes.
Comment 56 Rob Adams 2003-06-09 04:15:08 UTC
Created attachment 17342 [details] [review]
and here's the latest patch.
Comment 57 Rob Adams 2003-06-11 03:20:17 UTC
I'm attaching a new version of the patch.  This one adds increases
robustness against weird strut sizes by imposing a max strut size of
not quite half the width or height of the screen.  This is obviously
not a perfect solution as dock windows setting a strut could
theoretically be that big and then the window could be "lost" behind
the giant panel of doom, but I think that it's more likely that struts
larger than this are a result of a bug in setting the strut by the
dock app.

Also, this version of the patch implements the "iterate to a fixed
point" concept for the constraints, by re-enqueueing a window if
meta_window_constrain ends up changing its position.

This version of the patch ought to be good enough to commit to CVS.
Comment 58 Rob Adams 2003-06-11 03:20:43 UTC
Created attachment 17420 [details] [review]
latest patch
Comment 59 Havoc Pennington 2003-06-11 07:02:45 UTC
So I couldn't sleep and thought about this some and thought I'd write
it up. First, looking at your latest patch the first thing that occurs
to me is that we might consider separating out the "nuke winhints" and
"read partial struts property" parts of the patch to be committed
right away, then continue this bug with only the constraints.c stuff
so there's a smaller patch to work with as we finalize the hard bit. I
don't know how hard it would be for you to break the patch up at this
point.

The "ignore hints on fullscreen" change seems totally unrelated, in
the past I've wanted to avoid that, but maybe it's right.  We should
probably do same for maximized if we're going to do it. I think
there's already a bug for this where we could discuss that change to
avoid this bug getting out of control. The existing bug is about
maximize though.

OK, so on to my idea for how to implement the constraints stuff.
First I think the idea of deciding which struts apply based on current
position just can't be right, even if we iterate a couple times.  I'm
sure it happens to work mostly but I'm worried that's primarily
because when doing a move/resize you are moving in small increments.

Here is a suggested algorithm, I'll try to explain though it'd be 100x
easier with a whiteboard. This would be added as a reimplementation of
the constraint_onscreen constraint.

Remember: what we're trying to compute is the allowed dx/dy, so we can
constrain the move or resize deltas.

Assumption: Conceptually, the struts form a bunch of rectangles that
windows are not allowed to overlap. Think of a corner panel or
whatever.  The most horrible pathological case would be a big
screen-covering grid made of panels, like graph paper. The simple case
is a corner panel or 1-xinerama panel.  Anyhow, call all these
rectangles the "forbidden rectangles"

Note: unlike the other constraints, this one can't be expressed in
terms of "max" and "min"; for example, if you have a corner panel:

              |
              |   B
              |
  -------------
 
      A

And you move a window from point A to point B, then there are allowed
window positions on either side of the corner panel.

I think we might just ignore this for now.

Steps in the algorithm:

1. Take the requested (new) window rectangle, and iterate over all
forbidden rectangles. If the new window rect does not overlap any
forbidden rectangles (with meta_rectangle_intersect()), then simply
allow the new position. This might be A or B in the above diagram for
example.

2. If the window rect does overlap, then imagine a line drawn from
dx=0 dy=0 to dx=requested_dx dy=requested_dy. i.e. draw a line from A
to B in my ASCII art. Now, we want to find the dx,dy closest to the
requested dx,dy where the window will not overlap any forbidden areas.

To do so, the easiest algorithm is to simply search each pixel along
the line drawn from 0 delta to requested delta. I'd start by
implementing that just to see if the idea works. We want to prefer 
the larger deltas, so start searching at high delta and go to 0.

If it works, as an optimization we can check only intersection points
between this line and the edges of forbidden rectangles, rather than
checking all points along the line. But this optimization is probably
annoying to implement (although it should be fairly basic algebra), so
I'd skip it at first.


OK, so that seems pretty simple to code to me. The effect if all goes
well should be that you can move the window into any area where it
fits, and if you move the window where it doesn't fit, it will move as
far as it can while still fitting and then stop.

What it doesn't do is try to fit by varying dx and dy independently
(i.e. it doesn't search the entire rectangle covered by the region
(x,y) to (x+dx,y+dy), it just searches a diagonal line across that
rectangle). But, fuck it. ;-)

I may still be missing something important but this is my current line
of thought.

Comment 60 Rob Adams 2003-06-11 07:38:34 UTC
what you're trying to do is find a solution that minimizes the
difference between the requested position and the original position. 
This is certainly a reasonable idea, but I don't think that it's
really needed in this case.  Plus, as I'll explain below, it's not
perfectly general.

Maybe I should try to explain what's going on in the patch a little
bit better:
First, let's formulate the problem as a constraint satisfaction
problem.  The x and y coordinates of the window are the variables, and
the window positions are the solution space.  Each strut, screen edge,
etc. is a linear constraint.  If we add in an objective function as
the Euclidean distance between the resulting window position and the
requested user position, this problem becomes a linear program.

What my solution does it find all violated constraints, and corrects
the window position so that those constraints aren't violated.  This
technique is known as Heuristic Repair, and leads to excellent
solutions very fast, especially for easy solution spaces like ours.

The problem with heuristic repair is that it's generally not
guaranteed to find a solution in finite time.  For example, if we were
to allow arbitrary struts, it would be possible to place four of them
in such a way that the window would "bounce" around the four of them
indefinitely.  However, this would require that the struts be
sufficiently close together, and the way the code is written currently
isn't not possible for the struts to be sufficiently close. 
"Sufficiently close" here is defined basically as the
TITLEBAR_ONSCREEN value.  The result is that the window can be
affected by at most two strut constraints at any given time, and this
is why the constraint solver will terminate after two iterations (and
possibly a third iteration to verify the fixed point).
 
Now about the proposed solution above:  It took me a couple minutes to
notice to flaw, but the big problem here is that it assumes that the
"current" position of the window is not violating any constraints. 
For that to work, you would first need to compute a "feasible"
solution and then try to optimize along the line.

A big problem with this is that, though it's not very complicated, the
constraints are highly nonlinear so typical optimization techniques
don't work well.
Comment 61 Havoc Pennington 2003-06-11 15:46:48 UTC
OK, I don't understand what you've said there, so you're going to have 
to break down the algorithm for me into smaller steps for me. What the
code does doesn't map to what I would take your text to mean.

Why are you finding violated constraints using the forbidden areas
that the window is currently lined up with, rather than using the
forbidden areas the new window position will be lined up with?

The whole constraints.c thing is based on constraining a delta from 
current window size/position, so in some sense always does assume we 
have a sane starting point. We could try extending the 
line across the whole screen (rather than (x,y) to (x+dx,y+dy) we
could extend through (x,y) and over to a screen edge). I guess this 
is required if you want to make things work right when you move a
panel such that it now overlaps a window. In that case though we have
dx,dy of 0 so there's no known slope to the line; not sure what to 
do there.

Realized also that if you want to be able to drag up to a top panel
and then across, with the mouse inside the top panel, you would need 
to look for possible allowed positions along the line from (x,y) to
(x+dx,y) in addition, for example.
Comment 62 Rob Adams 2003-06-11 17:10:54 UTC
You can't assume that the "current" position isn't violating
constraints, because it very easily can.  For example, if you have a
window sitting on the top of the screen, and then create a new top
panel, the window's current position is now under the panel, and needs
to be moved.  In this case that line segment is of zero length, so you
can't really "extend" it, unless you want to consider every pixel on
the screen.  You could try drawing horizontal and vertical lines, and
find a place along those lines, but in general there won't always be
such a place because there could be two new struts that the window is
violating.  You'd have to try to generate diagonal lines running from
the window to perhaps some point on the edge of the work area.  I
think that if you added enough ugliness you might be able to get this
algorithm to work, but I doubt it would be as clean or as fast as the
heuristic repair technique used in this patch.

The other thing about the patch that I really like is that a top,
left, bottom, or right strut really means that -- windows get pushed
down, right, up, or left respectively when violating these struts.

The reason I was using the orig rectangle is because of the user_rect
thing: after a window has had its position constrained, the user_rect
remains unchanges.  So if for example a window was at 0,0 with a
y_delta of -20, and the code constrains it to a y_delta of 0, the next
time the code is called the "orig" rect will again be 0,0 and the
y_delta will again be -20.  So in effect, the orig rectangle is
usually closer to the final position of the window than the orig rect
+ x_delta and + y_delta.

But now I think that perhaps that was a mistake.  I'm attaching an
updated patch that changes this so that instead of using the orig rect
it will instead compute the current rect from the x_delta and y_delta,
and iterate on the deltas in constrain_move.  This means that it will
be sure to always constrain on the requested position and not on the
current position.  I'm pretty sure also that there's no need to
re-enqueue the resize from resize_internal now so this should make it
a bit faster as well.

This patch is quite large now.  What I think we should probably do is
commit at least everything but the get_outermost_ function to make
this easier to work with.  Alternatively, we could commit everything
(since the patch is working) and then tweak it from there.

And the fullscreen thing: yea that's kind of random.  I fixed that
while I was doing constraints hacking, and had intended to make it a
separate patch, but I guess it got buried ;-).

-Rob
Comment 63 Rob Adams 2003-06-11 17:11:33 UTC
Created attachment 17462 [details] [review]
use requested rect instead of orig rect
Comment 64 Rob Adams 2003-06-12 07:36:04 UTC
Created attachment 17480 [details] [review]
updated for current CVS.  Let's set a record for most revisions of one patch on a bug.
Comment 65 Rob Adams 2003-06-13 16:40:27 UTC
OK to commit, Havoc?  There are other patches I want to write, but
they all conflict with this.

Just because it's in CVS doesn't mean the change is irrevocable...
Comment 66 Rob Adams 2003-06-25 14:39:42 UTC
*** Bug 115937 has been marked as a duplicate of this bug. ***
Comment 67 Havoc Pennington 2003-06-25 22:07:56 UTC
OK, I read the latest patch now. I have some comments but they are all 
easier for me to just fix in CVS than to explain, so why not 
just commit and we'll touch it up over time.

Thanks!
Comment 68 Rob Adams 2003-06-26 03:46:03 UTC
OK.  It's committed.  I'm going to go ahead and close this bug.  We
can start a new one for other issues.

Also, if you could commit that spec patch Havoc that'd be great.  Let
me know if you want me to send it to you.
Comment 69 Rob Adams 2003-07-31 23:02:17 UTC
*** Bug 118819 has been marked as a duplicate of this bug. ***
Comment 70 Rob Adams 2003-08-18 19:20:09 UTC
*** Bug 120169 has been marked as a duplicate of this bug. ***
Comment 71 Rob Adams 2003-10-30 17:20:55 UTC
*** Bug 125851 has been marked as a duplicate of this bug. ***