Created attachment 30777 [details]
verbose debug log

            GList* link;
              link = g_list_find (window->screen->active_workspace->mru_list, 
                                  window);
              g_assert (link);

I tried looking at this a little bit.  I'd like to be able to duplicate, but I'm
having a hard time.  I have a few questions.  I believe I know the answers to
some, but I'm not sure I read the log right, and I'd like to make sure:

1. How many workspaces did you start with?
2. How many rows did you start with?
3. Which workspace did you start on?
4. Which workspace did you move to?
5. Were there windows on the workspace you started on?
6. Were there windows on the workspace you switched to?
7. Did you really use Ctrl-Alt-Tab to change workspaces (that's not what it
normally does)?  If so, what was the function that you reassigned Ctrl-Alt-Tab
to (e.g. switch to workspace 5, switch to workspace right, move window to
workspace down)?
8. Is the use of xinerama needed to trigger the bug?

Nevermind, after switching to sloppy focus I am able to trigger this.  Changing
the number of rows doesn't appear to be necessary.

Okay, so duplicating is a little easier.  With focus method of either click or
sloppy:

1) Add a new workspace with the workspace switcher
2) Move to that workspace (using keybindings, workspace switcher, or whatever)

With mouse focus, you also have to click on the panel or desktop after moving to
that workspace (which I wasn't doing originally and explains why I was having a
hard time duplicating).

The problem is that when we add new workspaces, we don't initialize anything in
them.  In particular, the mru_list is NULL.  I'll attach a patch momentarily.

Created attachment 30878 [details] [review]
Initialize workspaces; clean up two other warnings we were also getting

Okay, so I cheated and included two other fixes in this patch to remove some
warnings we were getting (and which I stumbled upon while testing this patch):

In window.c's meta_window_show, don't try to place a not-focused-on-map-window
below the desktop or the dock.	Doing so appears to just give a warning (from
the "g_return_if_fail (position >= 0);" in
meta_window_set_stack_position_no_sync), but all the same, it's cleaner to not
do that.

In workspace.c's meta_workspace_relocate_windows, we were trying to add windows
which were already on all workspaces to a different workspace.	Don't do that.

Comment on attachment 30878 [details] [review]
Initialize workspaces; clean up two other warnings we were also getting

I would fix the stacking below dock/desktop differently. The way the stack
works is that say you have windows in stack position 0 through 6, they may
really be like:

DESKTOPLAYER: 6
NORMALLAYER: 0, 1, 3, 4
DOCKLAYER: 2, 5

So I would rather not special case DOCK/DESKTOP in meta_window_show.

I think the right fix as set_stack_position_no_sync() is currently written, if
you are raising the window to get it "just below" you have to set it to
just_below->stack_position -1, and if you are lowering a window to get it just
below you have to set its new position to just_below->stack_position.
Because set_stack_position_new_sync() 
reshuffles the window currently at the destination position differently
depending on direction of motion. 

workspace_initialize_from()  - on_all_workspaces windows aren't normally in all
workspace->windows, so why is this needed?
A workspace with no windows should be allowed I think.

relocate_windows() - why can't you add a window that's on all workspaces to a
different workspace?

I might just need the small-words explanation again.

Oh!  I was pretty sure that I had previously seen the window-being-denied-focus
be set TWO windows below the active one in the stacking order.  I didn't at all
understand why, I had a hard time duplicating, and I wondered if it was just due
to something else strange I had done.  Your explanation appears to clear that
issue up too.  So, since these windows are always at the top of the stack when I
enter this function, I need to get rid of the " - 1".  :-)

I wasn't aware that on_all_workspace windows aren't normally in all
workspace->windows.  I was merely looking at the logic of
meta_workspace_add_window and trying to mimic it (since that seemed to be the
logical way to get the mru_list initialized).  Does the same hold true for
window->workspaces?

If you try to add a window that's on all workspaces to a different workspace,
the "g_return_if_fail (!meta_workspace_contains_window (workspace, window));"
line of meta_workspace_add_window kicks in (er, maybe "can kick in"?) and causes
metacity to emit a warning.  Harmless, but slightly annoying.  But if
on_all_workspaces windows aren't normally in all workspace->windows then I
probably need to revert that and we need to just allow the warning to be shown.

Let me know what to do about workspace->windows and window->workspaces.  I know
I need to add the windows to the mru_list but I was only modifying the other two
lists because I noticed they looked uninitialized as well and thought it might
be useful to change them while I was at it.

Hehe.  Okay, so the warning from "g_return_if_fail
(!meta_workspace_contains_window (workspace, window));" was being caused by my
adding the on_all_workspace windows to workspace->windows.  Getting rid of that
removes the need to do the check in the relocate windows and everything runs
smoothly.  I'll attach a patch in a minute that does this and fixes the stacking
the way you specified.

Created attachment 30937 [details] [review]
Updated patch

I think workspace->windows and window->workspaces are intended to correspond (a
window is in workspace->windows iff the workspace is in window->workspaces).
In both cases on_all_workspaces windows aren't in every workspace's window list,
only in the list for the space where the window was when it was stuck or unstuck.

For initialize_from(), it would seem more correct to me in workspace_new() to
just get the list of windows from the display (or screen I guess, workspaces are
per-screen) and put all on_all_workspaces windows from the screen in the mru list?

Created attachment 30951 [details] [review]
Round three...FIGHT!

Is this what you had in mind?

Comment on attachment 30951 [details] [review]
Round three...FIGHT!

Well, it's a bit roundabout; I'd use meta_screen_foreach_window(), or
meta_display_list_windows() filtered by screen.

Then you don't need the g_list_find() since you will only traverse each window
once and can't possibly get duplicates.

You could add meta_screen_list_windows perhaps, to simplify things.

Created attachment 30999 [details] [review]
So much for 'third time's a charm'  :-)

Comment on attachment 30999 [details] [review]
So much for 'third time's a charm'  :-)

Fourth time is good too ;-)

Committed.