Add support for stacking X and Wayland windows together

This breaks down the assumptions in stack-tracker.c and stack.c that
Mutter is only stacking X windows.

The stack tracker now tracks windows using a MetaStackWindow structure
which is a union with a type member so that X windows can be
distinguished from Wayland windows.

Some notable changes are:

Queued stack tracker operations that affect Wayland windows will not be
associated with an X serial number.

If an operation only affects a Wayland window and there are no queued
stack tracker operations ("unvalidated predictions") then the operation
is applied immediately since there is no server involved with changing
the stacking for Wayland windows.

The stack tracker can no longer respond to X events by turning them into
stack operations and discarding the predicted operations made prior to
that event because operations based on X events don't know anything
about the stacking of Wayland windows.

Instead of discarding old predictions the new approach is to trust the
predictions but whenever we receive an event from the server that
affects stacking we cross-reference with the predicted stack and check
for consistency. So e.g. if we have an event that says ADD window A then
we apply the predictions (up to the serial for that event) and verify
the predicted state includes a window A. Similarly if an event says
RAISE_ABOVE(B, C) we can apply the predictions (up to the serial for
that event) and verify that window B is above C.

If we ever receive spurious stacking events (with a serial older than we
would expect) or find an inconsistency (some things aren't possible to
predict from the compositor) then we hit a re-synchronization code-path
that will query the X server for the full stacking order and then use
that stack to walk through our combined stack and force the X windows to
match the just queried stack but avoiding disrupting the relative
stacking of Wayland windows. This will be relatively expensive but
shouldn't be hit for compositor initiated restacking operations where
our predictions should be accurate.

The code in core/stack.c that deals with synchronizing the window stack
with the X server had to be updated quite heavily. In general the patch
avoids changing the fundamental approach being used but most of the code
did need some amount of re-factoring to consider what re-stacking
operations actually involve X or not and when we need to restack X
windows we sometimes need to search for a suitable X sibling to restack
relative too since the closest siblings may be Wayland windows.

10 files changed, 1189 insertions, 356 deletions

diff --git a/src/core/core.c b/src/core/core.c
index 7583da1ea..59d7aac06 100644
--- a/src/core/core.c
+++ b/src/core/core.c
@@ -269,6 +269,8 @@ meta_core_lower_beneath_grab_window (Display *xdisplay,
   MetaDisplay *display;
   MetaScreen *screen;
   MetaWindow *grab_window;
+  MetaStackWindow stack_window;
+  MetaStackWindow stack_sibling;
 
   display = meta_display_for_x_display (xdisplay);
   screen = meta_display_screen_for_xwindow (display, xwindow);
@@ -281,9 +283,13 @@ meta_core_lower_beneath_grab_window (Display *xdisplay,
   changes.sibling = grab_window->frame ? grab_window->frame->xwindow
                                        : grab_window->xwindow;
 
+  stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  stack_window.x11.xwindow = xwindow;
+  stack_sibling.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  stack_sibling.x11.xwindow = changes.sibling;
   meta_stack_tracker_record_lower_below (screen->stack_tracker,
-                                         xwindow,
-                                         changes.sibling,
+                                         &stack_window,
+                                         &stack_sibling,
                                          XNextRequest (screen->display->xdisplay));
 
   meta_error_trap_push (display);
diff --git a/src/core/frame.c b/src/core/frame.c
index 2c48bb166..d7e254ecf 100644
--- a/src/core/frame.c
+++ b/src/core/frame.c
@@ -47,6 +47,7 @@ meta_window_ensure_frame (MetaWindow *window)
   XSetWindowAttributes attrs;
   Visual *visual;
   gulong create_serial;
+  MetaStackWindow stack_window;
   
   if (window->frame)
     return;
@@ -105,8 +106,10 @@ meta_window_ensure_frame (MetaWindow *window)
 						frame->rect.height,
 						frame->window->screen->number,
                                                 &create_serial);
+  stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  stack_window.x11.xwindow = frame->xwindow;
   meta_stack_tracker_record_add (window->screen->stack_tracker,
-                                 frame->xwindow,
+                                 &stack_window,
                                  create_serial);
 
   meta_verbose ("Frame for %s is 0x%lx\n", frame->window->desc, frame->xwindow);
@@ -138,8 +141,9 @@ meta_window_ensure_frame (MetaWindow *window)
   window->rect.x = 0;
   window->rect.y = 0;
 
+  stack_window.x11.xwindow = window->xwindow;
   meta_stack_tracker_record_remove (window->screen->stack_tracker,
-                                    window->xwindow,
+                                    &stack_window,
                                     XNextRequest (window->display->xdisplay));
   XReparentWindow (window->display->xdisplay,
                    window->xwindow,
@@ -174,6 +178,7 @@ meta_window_destroy_frame (MetaWindow *window)
 {
   MetaFrame *frame;
   MetaFrameBorders borders;
+  MetaStackWindow stack_window;
   
   if (window->frame == NULL)
     return;
@@ -200,8 +205,10 @@ meta_window_destroy_frame (MetaWindow *window)
                   "Incrementing unmaps_pending on %s for reparent back to root\n", window->desc);
       window->unmaps_pending += 1;
     }
+  stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  stack_window.x11.xwindow = window->xwindow;
   meta_stack_tracker_record_add (window->screen->stack_tracker,
-                                 window->xwindow,
+                                 &stack_window,
                                  XNextRequest (window->display->xdisplay));
   XReparentWindow (window->display->xdisplay,
                    window->xwindow,
diff --git a/src/core/screen.c b/src/core/screen.c
index e3c997eb4..073a8af71 100644
--- a/src/core/screen.c
+++ b/src/core/screen.c
@@ -612,6 +612,7 @@ meta_screen_create_guard_window (Display *xdisplay, MetaScreen *screen)
   XSetWindowAttributes attributes;
   Window guard_window;
   gulong create_serial;
+  MetaStackWindow stack_window;
   
   attributes.event_mask = NoEventMask;
   attributes.override_redirect = True;
@@ -644,12 +645,14 @@ meta_screen_create_guard_window (Display *xdisplay, MetaScreen *screen)
     XISelectEvents (xdisplay, guard_window, &mask, 1);
   }
 
+  stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  stack_window.x11.xwindow = guard_window;
   meta_stack_tracker_record_add (screen->stack_tracker,
-                                 guard_window,
+                                 &stack_window,
                                  create_serial);
 
   meta_stack_tracker_record_lower (screen->stack_tracker,
-                                   guard_window,
+                                   &stack_window,
                                    XNextRequest (xdisplay));
   XLowerWindow (xdisplay, guard_window);
   XMapWindow (xdisplay, guard_window);
@@ -1917,12 +1920,15 @@ meta_screen_tile_preview_update_timeout (gpointer data)
     {
       Window xwindow;
       gulong create_serial;
+      MetaStackWindow stack_window;
 
       screen->tile_preview = meta_tile_preview_new (screen->number);
       xwindow = meta_tile_preview_get_xwindow (screen->tile_preview,
                                                &create_serial);
+      stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+      stack_window.x11.xwindow = xwindow;
       meta_stack_tracker_record_add (screen->stack_tracker,
-                                     xwindow,
+                                     &stack_window,
                                      create_serial);
     }
 
diff --git a/src/core/stack-tracker.c b/src/core/stack-tracker.c
index 85deca622..fb26b6b21 100644
--- a/src/core/stack-tracker.c
+++ b/src/core/stack-tracker.c
@@ -98,28 +98,29 @@ union _MetaStackOp
   struct {
     MetaStackOpType type;
     gulong serial;
+    MetaStackWindow window;
   } any;
   struct {
     MetaStackOpType type;
     gulong serial;
-    Window window;
+    MetaStackWindow window;
   } add;
   struct {
     MetaStackOpType type;
     gulong serial;
-    Window window;
+    MetaStackWindow window;
   } remove;
   struct {
     MetaStackOpType type;
     gulong serial;
-    Window window;
-    Window sibling;
+    MetaStackWindow window;
+    MetaStackWindow sibling;
   } raise_above;
   struct {
     MetaStackOpType type;
     gulong serial;
-    Window window;
-    Window sibling;
+    MetaStackWindow window;
+    MetaStackWindow sibling;
   } lower_below;
 };
 
@@ -130,20 +131,25 @@ struct _MetaStackTracker
   /* This is the last state of the stack as based on events received
    * from the X server.
    */
-  GArray *server_stack;
+  GArray *xserver_stack;
 
   /* This is the serial of the last request we made that was reflected
-   * in server_stack
+   * in xserver_stack
    */
-  gulong server_serial;
+  gulong xserver_serial;
+
+  /* A combined stack containing X and Wayland windows but without
+   * any unverified operations applied. */
+  GArray *verified_stack;
 
   /* This is a queue of requests we've made to change the stacking order,
    * where we haven't yet gotten a reply back from the server.
    */
-  GQueue *queued_requests;
+  GQueue *unverified_predictions;
 
-  /* This is how we think the stack is, based on server_stack, and
-   * on requests we've made subsequent to server_stack
+  /* This is how we think the stack is, based on verified_stack, and
+   * on the unverified_predictions we've made subsequent to
+   * verified_stack.
    */
   GArray *predicted_stack;
 
@@ -153,36 +159,81 @@ struct _MetaStackTracker
   guint sync_stack_later;
 };
 
+static gboolean
+meta_stack_window_is_set (const MetaStackWindow *window)
+{
+  if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+    return window->x11.xwindow == None ? FALSE : TRUE;
+  else
+    return window->wayland.meta_window ? TRUE : FALSE;
+}
+
+gboolean
+meta_stack_window_equal (const MetaStackWindow *a,
+                         const MetaStackWindow *b)
+{
+  if (a->any.type == b->any.type)
+    {
+      if (a->any.type == META_WINDOW_CLIENT_TYPE_X11)
+        return a->x11.xwindow == b->x11.xwindow;
+      else
+        return a->wayland.meta_window == b->wayland.meta_window;
+    }
+  else
+    return FALSE;
+}
+
+static char *
+get_window_id (MetaStackWindow *window)
+{
+  if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+    return g_strdup_printf ("X11:%lx", window->x11.xwindow);
+  else
+    return g_strdup_printf ("Wayland:%p", window->wayland.meta_window);
+}
+
 static void
 meta_stack_op_dump (MetaStackOp *op,
 		    const char  *prefix,
 		    const char  *suffix)
 {
+  char *window_id = get_window_id (&op->any.window);
+
   switch (op->any.type)
     {
     case STACK_OP_ADD:
-      meta_topic (META_DEBUG_STACK, "%sADD(%#lx; %ld)%s",
-		  prefix, op->add.window, op->any.serial, suffix);
+      meta_topic (META_DEBUG_STACK, "%sADD(%s; %ld)%s",
+		  prefix, window_id, op->any.serial, suffix);
       break;
     case STACK_OP_REMOVE:
-      meta_topic (META_DEBUG_STACK, "%sREMOVE(%#lx; %ld)%s",
-		  prefix, op->add.window, op->any.serial, suffix);
+      meta_topic (META_DEBUG_STACK, "%sREMOVE(%s; %ld)%s",
+		  prefix, window_id, op->any.serial, suffix);
       break;
     case STACK_OP_RAISE_ABOVE:
-      meta_topic (META_DEBUG_STACK, "%sRAISE_ABOVE(%#lx, %#lx; %ld)%s",
-		  prefix,
-                  op->raise_above.window, op->raise_above.sibling,
-                  op->any.serial,
-                  suffix);
-      break;
+      {
+        char *sibling_id = get_window_id (&op->raise_above.sibling);
+        meta_topic (META_DEBUG_STACK, "%sRAISE_ABOVE(%s, %s; %ld)%s",
+                    prefix,
+                    window_id, sibling_id,
+                    op->any.serial,
+                    suffix);
+        g_free (sibling_id);
+        break;
+      }
     case STACK_OP_LOWER_BELOW:
-      meta_topic (META_DEBUG_STACK, "%sLOWER_BELOW(%#lx, %#lx; %ld)%s",
-		  prefix,
-                  op->lower_below.window, op->lower_below.sibling,
-                  op->any.serial,
-                  suffix);
-      break;
+      {
+        char *sibling_id = get_window_id (&op->lower_below.sibling);
+        meta_topic (META_DEBUG_STACK, "%sLOWER_BELOW(%s, %s; %ld)%s",
+                    prefix,
+                    window_id, sibling_id,
+                    op->any.serial,
+                    suffix);
+        g_free (sibling_id);
+        break;
+      }
     }
+
+  g_free (window_id);
 }
 
 static void
@@ -193,23 +244,42 @@ meta_stack_tracker_dump (MetaStackTracker *tracker)
 
   meta_topic (META_DEBUG_STACK, "MetaStackTracker state (screen=%d)\n", tracker->screen->number);
   meta_push_no_msg_prefix ();
-  meta_topic (META_DEBUG_STACK, "  server_serial: %ld\n", tracker->server_serial);
-  meta_topic (META_DEBUG_STACK, "  server_stack: ");
-  for (i = 0; i < tracker->server_stack->len; i++)
-    meta_topic (META_DEBUG_STACK, "  %#lx", g_array_index (tracker->server_stack, Window, i));
-  if (tracker->predicted_stack)
+  meta_topic (META_DEBUG_STACK, "  xserver_serial: %ld\n", tracker->xserver_serial);
+  meta_topic (META_DEBUG_STACK, "  xserver_stack: ");
+  for (i = 0; i < tracker->xserver_stack->len; i++)
     {
-      meta_topic (META_DEBUG_STACK, "\n  predicted_stack: ");
-      for (i = 0; i < tracker->predicted_stack->len; i++)
-	meta_topic (META_DEBUG_STACK, "  %#lx", g_array_index (tracker->predicted_stack, Window, i));
+      MetaStackWindow *window = &g_array_index (tracker->xserver_stack, MetaStackWindow, i);
+      char *window_id = get_window_id (window);
+      meta_topic (META_DEBUG_STACK, "  %s", window_id);
+      g_free (window_id);
+    }
+  meta_topic (META_DEBUG_STACK, "\n  verfied_stack: ");
+  for (i = 0; i < tracker->verified_stack->len; i++)
+    {
+      MetaStackWindow *window = &g_array_index (tracker->verified_stack, MetaStackWindow, i);
+      char *window_id = get_window_id (window);
+      meta_topic (META_DEBUG_STACK, "  %s", window_id);
+      g_free (window_id);
     }
-  meta_topic (META_DEBUG_STACK, "\n  queued_requests: [");
-  for (l = tracker->queued_requests->head; l; l = l->next)
+  meta_topic (META_DEBUG_STACK, "\n  unverified_predictions: [");
+  for (l = tracker->unverified_predictions->head; l; l = l->next)
     {
       MetaStackOp *op = l->data;
       meta_stack_op_dump (op, "", l->next ? ", " : "");
     }
   meta_topic (META_DEBUG_STACK, "]\n");
+  if (tracker->predicted_stack)
+    {
+      meta_topic (META_DEBUG_STACK, "\n  predicted_stack: ");
+      for (i = 0; i < tracker->predicted_stack->len; i++)
+        {
+          MetaStackWindow *window = &g_array_index (tracker->predicted_stack, MetaStackWindow, i);
+          char *window_id = get_window_id (window);
+          meta_topic (META_DEBUG_STACK, "  %s", window_id);
+          g_free (window_id);
+        }
+    }
+  meta_topic (META_DEBUG_STACK, "\n");
   meta_pop_no_msg_prefix ();
 }
 
@@ -220,42 +290,57 @@ meta_stack_op_free (MetaStackOp *op)
 }
 
 static int
-find_window (GArray *stack,
-	     Window  window)
+find_window (GArray *window_stack,
+             MetaStackWindow *window)
 {
   guint i;
 
-  for (i = 0; i < stack->len; i++)
-    if (g_array_index (stack, Window, i) == window)
-      return i;
+  for (i = 0; i < window_stack->len; i++)
+    {
+      MetaStackWindow *current = &g_array_index (window_stack, MetaStackWindow, i);
+      if (current->any.type == window->any.type)
+        {
+          if (current->any.type == META_WINDOW_CLIENT_TYPE_X11 &&
+              current->x11.xwindow == window->x11.xwindow)
+            return i;
+          else
+            if (current->wayland.meta_window == window->wayland.meta_window)
+              return i;
+        }
+    }
 
   return -1;
 }
 
 /* Returns TRUE if stack was changed */
 static gboolean
-move_window_above (GArray *stack,
-                   Window  window,
-                   int     old_pos,
-                   int     above_pos)
+move_window_above (GArray          *stack,
+                   MetaStackWindow *window,
+                   int              old_pos,
+                   int              above_pos)
 {
+  /* Copy the window by-value before we start shifting things around
+   * in the stack in case window points into the stack itself. */
+  MetaStackWindow window_val = *window;
   int i;
 
   if (old_pos < above_pos)
     {
       for (i = old_pos; i < above_pos; i++)
-	g_array_index (stack, Window, i) = g_array_index (stack, Window, i + 1);
+	g_array_index (stack, MetaStackWindow, i) =
+          g_array_index (stack, MetaStackWindow, i + 1);
 
-      g_array_index (stack, Window, above_pos) = window;
+      g_array_index (stack, MetaStackWindow, above_pos) = window_val;
 
       return TRUE;
     }
   else if (old_pos > above_pos + 1)
     {
       for (i = old_pos; i > above_pos + 1; i--)
-	g_array_index (stack, Window, i) = g_array_index (stack, Window, i - 1);
+	g_array_index (stack, MetaStackWindow, i) =
+          g_array_index (stack, MetaStackWindow, i - 1);
 
-      g_array_index (stack, Window, above_pos + 1) = window;
+      g_array_index (stack, MetaStackWindow, above_pos + 1) = window_val;
 
       return TRUE;
     }
@@ -272,11 +357,13 @@ meta_stack_op_apply (MetaStackOp *op,
     {
     case STACK_OP_ADD:
       {
-	int old_pos = find_window (stack, op->add.window);
+	int old_pos = find_window (stack, &op->add.window);
 	if (old_pos >= 0)
 	  {
-	    g_warning ("STACK_OP_ADD: window %#lx already in stack",
-		       op->add.window);
+            char *window_id = get_window_id (&op->add.window);
+	    g_warning ("STACK_OP_ADD: window %s already in stack",
+		       window_id);
+            g_free (window_id);
 	    return FALSE;
 	  }
 
@@ -285,11 +372,13 @@ meta_stack_op_apply (MetaStackOp *op,
       }
     case STACK_OP_REMOVE:
       {
-	int old_pos = find_window (stack, op->remove.window);
+	int old_pos = find_window (stack, &op->remove.window);
 	if (old_pos < 0)
 	  {
-	    g_warning ("STACK_OP_REMOVE: window %#lx not in stack",
-		       op->remove.window);
+            char *window_id = get_window_id (&op->remove.window);
+	    g_warning ("STACK_OP_REMOVE: window %s not in stack",
+		       window_id);
+            g_free (window_id);
 	    return FALSE;
 	  }
 
@@ -298,22 +387,26 @@ meta_stack_op_apply (MetaStackOp *op,
       }
     case STACK_OP_RAISE_ABOVE:
       {
-	int old_pos = find_window (stack, op->raise_above.window);
+	int old_pos = find_window (stack, &op->raise_above.window);
 	int above_pos;
 	if (old_pos < 0)
 	  {
-	    g_warning ("STACK_OP_RAISE_ABOVE: window %#lx not in stack",
-		       op->raise_above.window);
+            char *window_id = get_window_id (&op->raise_above.window);
+	    g_warning ("STACK_OP_RAISE_ABOVE: window %s not in stack",
+		       window_id);
+            g_free (window_id);
 	    return FALSE;
 	  }
 
-	if (op->raise_above.sibling != None)
+        if (meta_stack_window_is_set (&op->raise_above.sibling))
 	  {
-	    above_pos = find_window (stack, op->raise_above.sibling);
+	    above_pos = find_window (stack, &op->raise_above.sibling);
 	    if (above_pos < 0)
 	      {
-		g_warning ("STACK_OP_RAISE_ABOVE: sibling window %#lx not in stack",
-			   op->raise_above.sibling);
+                char *sibling_id = get_window_id (&op->raise_above.sibling);
+		g_warning ("STACK_OP_RAISE_ABOVE: sibling window %s not in stack",
+			   sibling_id);
+                g_free (sibling_id);
 		return FALSE;
 	      }
 	  }
@@ -322,26 +415,30 @@ meta_stack_op_apply (MetaStackOp *op,
 	    above_pos = -1;
 	  }
 
-	return move_window_above (stack, op->raise_above.window, old_pos, above_pos);
+	return move_window_above (stack, &op->raise_above.window, old_pos, above_pos);
       }
     case STACK_OP_LOWER_BELOW:
       {
-	int old_pos = find_window (stack, op->lower_below.window);
+	int old_pos = find_window (stack, &op->lower_below.window);
 	int above_pos;
 	if (old_pos < 0)
 	  {
-	    g_warning ("STACK_OP_LOWER_BELOW: window %#lx not in stack",
-		       op->lower_below.window);
+            char *window_id = get_window_id (&op->lower_below.window);
+	    g_warning ("STACK_OP_LOWER_BELOW: window %s not in stack",
+		       window_id);
+            g_free (window_id);
 	    return FALSE;
 	  }
 
-	if (op->lower_below.sibling != None)
+        if (meta_stack_window_is_set (&op->lower_below.sibling))
 	  {
-	    int below_pos = find_window (stack, op->lower_below.sibling);
+	    int below_pos = find_window (stack, &op->lower_below.sibling);
 	    if (below_pos < 0)
 	      {
-		g_warning ("STACK_OP_LOWER_BELOW: sibling window %#lx not in stack",
-			   op->lower_below.sibling);
+                char *sibling_id = get_window_id (&op->lower_below.sibling);
+		g_warning ("STACK_OP_LOWER_BELOW: sibling window %s not in stack",
+			   sibling_id);
+                g_free (sibling_id);
 		return FALSE;
 	      }
 
@@ -352,7 +449,7 @@ meta_stack_op_apply (MetaStackOp *op,
 	    above_pos = stack->len - 1;
 	  }
 
-	return move_window_above (stack, op->lower_below.window, old_pos, above_pos);
+	return move_window_above (stack, &op->lower_below.window, old_pos, above_pos);
       }
     }
 
@@ -361,37 +458,65 @@ meta_stack_op_apply (MetaStackOp *op,
 }
 
 static GArray *
-copy_stack (Window *windows,
-	    guint   n_windows)
+copy_stack (GArray *stack)
 {
-  GArray *stack = g_array_new (FALSE, FALSE, sizeof (Window));
+  GArray *copy = g_array_sized_new (FALSE, FALSE, sizeof (MetaStackWindow), stack->len);
 
-  g_array_set_size (stack, n_windows);
-  memcpy (stack->data, windows, sizeof (Window) * n_windows);
+  g_array_set_size (copy, stack->len);
 
-  return stack;
+  memcpy (copy->data, stack->data, sizeof (MetaStackWindow) * stack->len);
+
+  return copy;
 }
 
-MetaStackTracker *
-meta_stack_tracker_new (MetaScreen *screen)
+static void
+requery_xserver_stack (MetaStackTracker *tracker)
 {
-  MetaStackTracker *tracker;
+  MetaScreen *screen = tracker->screen;
   Window ignored1, ignored2;
   Window *children;
   guint n_children;
+  guint i;
 
-  tracker = g_new0 (MetaStackTracker, 1);
-  tracker->screen = screen;
+  if (tracker->xserver_stack)
+    g_array_free (tracker->xserver_stack, TRUE);
 
-  tracker->server_serial = XNextRequest (screen->display->xdisplay);
+  tracker->xserver_serial = XNextRequest (screen->display->xdisplay);
 
   XQueryTree (screen->display->xdisplay,
               screen->xroot,
               &ignored1, &ignored2, &children, &n_children);
-  tracker->server_stack = copy_stack (children, n_children);
+
+  tracker->xserver_stack =
+    g_array_sized_new (FALSE, FALSE, sizeof (MetaStackWindow), n_children);
+  g_array_set_size (tracker->xserver_stack, n_children);
+
+  for (i = 0; i < n_children; i++)
+    {
+      MetaStackWindow *window =
+        &g_array_index (tracker->xserver_stack, MetaStackWindow, i);
+      window->any.type = META_WINDOW_CLIENT_TYPE_X11;
+      window->x11.xwindow = children[i];
+    }
+
   XFree (children);
+}
+
+MetaStackTracker *
+meta_stack_tracker_new (MetaScreen *screen)
+{
+  MetaStackTracker *tracker;
+
+  tracker = g_new0 (MetaStackTracker, 1);
+  tracker->screen = screen;
+
+  requery_xserver_stack (tracker);
+
+  tracker->verified_stack = copy_stack (tracker->xserver_stack);
 
-  tracker->queued_requests = g_queue_new ();
+  tracker->unverified_predictions = g_queue_new ();
+
+  meta_stack_tracker_dump (tracker);
 
   return tracker;
 }
@@ -402,23 +527,38 @@ meta_stack_tracker_free (MetaStackTracker *tracker)
   if (tracker->sync_stack_later)
     meta_later_remove (tracker->sync_stack_later);
 
-  g_array_free (tracker->server_stack, TRUE);
+  g_array_free (tracker->xserver_stack, TRUE);
+  g_array_free (tracker->verified_stack, TRUE);
   if (tracker->predicted_stack)
     g_array_free (tracker->predicted_stack, TRUE);
 
-  g_queue_foreach (tracker->queued_requests, (GFunc)meta_stack_op_free, NULL);
-  g_queue_free (tracker->queued_requests);
-  tracker->queued_requests = NULL;
+  g_queue_foreach (tracker->unverified_predictions, (GFunc)meta_stack_op_free, NULL);
+  g_queue_free (tracker->unverified_predictions);
+  tracker->unverified_predictions = NULL;
 
   g_free (tracker);
 }
 
 static void
-stack_tracker_queue_request (MetaStackTracker *tracker,
-			     MetaStackOp      *op)
+stack_tracker_apply_prediction (MetaStackTracker *tracker,
+			        MetaStackOp      *op)
 {
-  meta_stack_op_dump (op, "Queueing: ", "\n");
-  g_queue_push_tail (tracker->queued_requests, op);
+  /* If this is a wayland operation then it's implicitly verified so
+   * we can apply it immediately so long as it doesn't depend on any
+   * unverified X operations...
+   */
+  if (op->any.window.any.type == META_WINDOW_CLIENT_TYPE_WAYLAND &&
+      tracker->unverified_predictions->length == 0)
+    {
+      if (meta_stack_op_apply (op, tracker->verified_stack))
+        meta_stack_tracker_queue_sync_stack (tracker);
+    }
+  else
+    {
+      meta_stack_op_dump (op, "Predicting: ", "\n");
+      g_queue_push_tail (tracker->unverified_predictions, op);
+    }
+
   if (!tracker->predicted_stack ||
       meta_stack_op_apply (op, tracker->predicted_stack))
     meta_stack_tracker_queue_sync_stack (tracker);
@@ -427,44 +567,50 @@ stack_tracker_queue_request (MetaStackTracker *tracker,
 }
 
 void
-meta_stack_tracker_record_add (MetaStackTracker *tracker,
-			       Window            window,
-			       gulong            serial)
+meta_stack_tracker_record_add (MetaStackTracker       *tracker,
+                               const MetaStackWindow  *window,
+			       gulong                  serial)
 {
   MetaStackOp *op = g_slice_new (MetaStackOp);
 
   op->any.type = STACK_OP_ADD;
   op->any.serial = serial;
-  op->add.window = window;
+  op->any.window = *window;
 
-  stack_tracker_queue_request (tracker, op);
+  stack_tracker_apply_prediction (tracker, op);
 }
 
 void
-meta_stack_tracker_record_remove (MetaStackTracker *tracker,
-				  Window            window,
-				  gulong            serial)
+meta_stack_tracker_record_remove (MetaStackTracker      *tracker,
+                                  const MetaStackWindow *window,
+				  gulong                 serial)
 {
   MetaStackOp *op = g_slice_new (MetaStackOp);
 
   op->any.type = STACK_OP_REMOVE;
   op->any.serial = serial;
-  op->remove.window = window;
+  op->any.window = *window;
 
-  stack_tracker_queue_request (tracker, op);
+  stack_tracker_apply_prediction (tracker, op);
 }
 
 void
-meta_stack_tracker_record_restack_windows (MetaStackTracker *tracker,
-					   Window           *windows,
-					   int               n_windows,
-					   gulong            serial)
+meta_stack_tracker_record_restack_windows (MetaStackTracker       *tracker,
+                                           const MetaStackWindow  *windows,
+					   int                     n_windows,
+					   gulong                  serial)
 {
   int i;
+  int n_x_windows = 0;
 
   /* XRestackWindows() isn't actually a X requests - it's broken down
    * by XLib into a series of XConfigureWindow(StackMode=below); we
-   * mirror that exactly here.
+   * mirror that here.
+   *
+   * Since there may be a mixture of X and wayland windows in the
+   * stack it's ambiguous which operations we should associate with an
+   * X serial number. One thing we do know though is that there will
+   * be (n_x_window - 1) X requests made.
    *
    * Aside: Having a separate StackOp for this would be possible to
    * get some extra efficiency in memory allocation and in applying
@@ -473,79 +619,406 @@ meta_stack_tracker_record_restack_windows (MetaStackTracker *tracker,
    * events with intermediate serials, set n_complete rather than
    * removing the op from the queue.
    */
+  if (n_windows && windows[0].any.type == META_WINDOW_CLIENT_TYPE_X11)
+    n_x_windows++;
   for (i = 0; i < n_windows - 1; i++)
-    meta_stack_tracker_record_lower_below (tracker, windows[i + 1], windows[i],
-					   serial + i);
+    {
+      const MetaStackWindow *lower = &windows[i + 1];
+      gboolean involves_x = FALSE;
+
+      if (lower->any.type == META_WINDOW_CLIENT_TYPE_X11)
+        {
+          n_x_windows++;
+
+          /* Since the first X window is a reference point we only
+           * assoicate a serial number with the operations involving
+           * later X windows. */
+          if (n_x_windows > 1)
+            involves_x = TRUE;
+        }
+
+      meta_stack_tracker_record_lower_below (tracker, lower, &windows[i],
+                                             involves_x ? serial++ : 0);
+    }
 }
 
 void
-meta_stack_tracker_record_raise_above (MetaStackTracker *tracker,
-				       Window            window,
-				       Window            sibling,
-				       gulong            serial)
+meta_stack_tracker_record_raise_above (MetaStackTracker       *tracker,
+                                       const MetaStackWindow  *window,
+                                       const MetaStackWindow  *sibling,
+				       gulong                  serial)
 {
   MetaStackOp *op = g_slice_new (MetaStackOp);
 
   op->any.type = STACK_OP_RAISE_ABOVE;
   op->any.serial = serial;
-  op->raise_above.window = window;
-  op->raise_above.sibling = sibling;
+  op->any.window = *window;
+  if (sibling)
+    op->raise_above.sibling = *sibling;
+  else
+    {
+      op->raise_above.sibling.any.type = META_WINDOW_CLIENT_TYPE_X11;
+      op->raise_above.sibling.x11.xwindow = None;
+    }
 
-  stack_tracker_queue_request (tracker, op);
+  stack_tracker_apply_prediction (tracker, op);
 }
 
 void
-meta_stack_tracker_record_lower_below (MetaStackTracker *tracker,
-				       Window            window,
-				       Window            sibling,
-				       gulong            serial)
+meta_stack_tracker_record_lower_below (MetaStackTracker       *tracker,
+                                       const MetaStackWindow  *window,
+                                       const MetaStackWindow  *sibling,
+				       gulong                  serial)
 {
   MetaStackOp *op = g_slice_new (MetaStackOp);
 
   op->any.type = STACK_OP_LOWER_BELOW;
   op->any.serial = serial;
-  op->lower_below.window = window;
-  op->lower_below.sibling = sibling;
+  op->any.window = *window;
+  if (sibling)
+    op->lower_below.sibling = *sibling;
+  else
+    {
+      op->lower_below.sibling.any.type = META_WINDOW_CLIENT_TYPE_X11;
+      op->lower_below.sibling.x11.xwindow = None;
+    }
 
-  stack_tracker_queue_request (tracker, op);
+  stack_tracker_apply_prediction (tracker, op);
 }
 
 void
-meta_stack_tracker_record_lower (MetaStackTracker *tracker,
-				 Window            window,
-				 gulong            serial)
+meta_stack_tracker_record_lower (MetaStackTracker       *tracker,
+                                 const MetaStackWindow  *window,
+				 gulong                  serial)
 {
-  meta_stack_tracker_record_raise_above (tracker, window, None, serial);
+  meta_stack_tracker_record_raise_above (tracker, window, NULL, serial);
 }
 
-static void
-stack_tracker_event_received (MetaStackTracker *tracker,
-			      MetaStackOp      *op)
+/* @op is an operation derived from an X event from the server and we
+ * want to verify that our predicted operations are consistent with
+ * what's being reported by the X server.
+ *
+ * NB: Since our stack may actually be a mixture of X and Wayland
+ * clients we can't simply apply these operations derived from X
+ * events onto our stack and discard old predictions because these
+ * operations aren't aware of wayland windows.
+ *
+ * This function applies all the unverified predicted operations up to
+ * the given @serial onto the verified_stack so that we can check the
+ * stack for consistency with the given X operation.
+ *
+ * Return value: %TRUE if the predicted state is consistent with
+ * receiving the given @op from X, else %FALSE.
+ *
+ * @modified will be set to %TRUE if tracker->verified_stack is
+ * changed by applying any newly validated operations, else %FALSE.
+ */
+static gboolean
+stack_tracker_verify_predictions (MetaStackTracker *tracker,
+                                  MetaStackOp      *op,
+                                  gboolean         *modified)
 {
-  gboolean need_sync = FALSE;
+  GArray *tmp_predicted_stack = NULL;
+  GArray *predicted_stack;
+  gboolean modified_stack = FALSE;
 
-  meta_stack_op_dump (op, "Stack op event received: ", "\n");
+  /* Wayland operations don't need to be verified and shouldn't end up
+   * passed to this api. */
+  g_return_val_if_fail (op->any.window.any.type == META_WINDOW_CLIENT_TYPE_X11, FALSE);
 
-  if (op->any.serial < tracker->server_serial)
-    return;
+  if (tracker->unverified_predictions->length)
+    {
+      GList *l;
+
+      tmp_predicted_stack = predicted_stack = copy_stack (tracker->verified_stack);
+
+      for (l = tracker->unverified_predictions->head; l; l = l->next)
+        {
+          MetaStackOp *current_op = l->data;
+
+          if (current_op->any.serial > op->any.serial)
+            break;
+
+          modified_stack |= meta_stack_op_apply (current_op, predicted_stack);
+        }
+    }
+  else
+    predicted_stack = tracker->verified_stack;
 
-  tracker->server_serial = op->any.serial;
+  switch (op->any.type)
+    {
+    case STACK_OP_ADD:
+      if (!find_window (predicted_stack, &op->any.window))
+        {
+          char *window_id = get_window_id (&op->any.window);
+          meta_topic (META_DEBUG_STACK, "Verify STACK_OP_ADD: window %s not found\n",
+                      window_id);
+          g_free (window_id);
+          goto not_verified;
+        }
+      break;
+    case STACK_OP_REMOVE:
+      if (find_window (predicted_stack, &op->any.window))
+        {
+          char *window_id = get_window_id (&op->any.window);
+          meta_topic (META_DEBUG_STACK, "Verify STACK_OP_REMOVE: window %s was unexpectedly found\n",
+                      window_id);
+          g_free (window_id);
+          goto not_verified;
+        }
+      break;
+    case STACK_OP_RAISE_ABOVE:
+      {
+        Window last_xwindow = None;
+        char *window_id;
+        unsigned int i;
+
+        /* This code is only intended for verifying operations based
+         * on XEvents where we can assume the sibling refers to
+         * another X window...  */
+        g_return_val_if_fail (op->raise_above.sibling.any.type ==
+                              META_WINDOW_CLIENT_TYPE_X11, FALSE);
+
+        for (i = 0; i < predicted_stack->len; i++)
+          {
+            MetaStackWindow *window = &g_array_index (predicted_stack, MetaStackWindow, i);
+
+            if (meta_stack_window_equal (window, &op->any.window))
+              {
+                if (last_xwindow == op->raise_above.sibling.x11.xwindow)
+                  goto verified;
+                else
+                  goto not_verified;
+              }
+
+            if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+              last_xwindow = window->x11.xwindow;
+          }
+
+        window_id = get_window_id (&op->any.window);
+        meta_topic (META_DEBUG_STACK, "Verify STACK_OP_RAISE_ABOVE: window %s not found\n",
+                    window_id);
+        g_free (window_id);
+        goto not_verified;
+      }
+    case STACK_OP_LOWER_BELOW:
+      g_warn_if_reached (); /* No X events currently lead to this path */
+      goto not_verified;
+    }
 
-  if (meta_stack_op_apply (op, tracker->server_stack))
-    need_sync = TRUE;
+verified:
 
-  while (tracker->queued_requests->head)
+  /* We can free the operations which we have now verified... */
+  while (tracker->unverified_predictions->head)
     {
-      MetaStackOp *queued_op = tracker->queued_requests->head->data;
+      MetaStackOp *queued_op = tracker->unverified_predictions->head->data;
+
       if (queued_op->any.serial > op->any.serial)
 	break;
 
-      g_queue_pop_head (tracker->queued_requests);
+      g_queue_pop_head (tracker->unverified_predictions);
       meta_stack_op_free (queued_op);
-      need_sync = TRUE;
     }
 
-  if (need_sync)
+  *modified = modified_stack;
+  if (modified_stack)
+    {
+      g_array_free (tracker->verified_stack, TRUE);
+      tracker->verified_stack = predicted_stack;
+    }
+  else if (tmp_predicted_stack)
+    g_array_free (tmp_predicted_stack, TRUE);
+
+  return TRUE;
+
+not_verified:
+
+  if (tmp_predicted_stack)
+    g_array_free (tmp_predicted_stack, TRUE);
+
+  if (tracker->predicted_stack)
+    {
+      g_array_free (tracker->predicted_stack, TRUE);
+      tracker->predicted_stack = NULL;
+    }
+
+  *modified = FALSE;
+
+  return FALSE;
+}
+
+/* If we find that our predicted state is not consistent with what the
+ * X server is reporting to us then this function can re-query and
+ * re-synchronize verified_stack with the X server stack while
+ * hopefully not disrupting the relative stacking of Wayland windows.
+ *
+ * Return value: %TRUE if the verified stack was modified with respect
+ * to the predicted stack else %FALSE.
+ *
+ * Note: ->predicted_stack will be cleared by this function if
+ * ->verified_stack had to be modified when re-synchronizing.
+ */
+static gboolean
+resync_verified_stack_with_xserver_stack (MetaStackTracker *tracker)
+{
+  GList *l;
+  unsigned int i, j;
+  MetaStackWindow *expected_xwindow;
+  gboolean modified_stack;
+
+  /* Overview of the algorithm:
+   *
+   * - Re-query the complete X window stack from the X server via
+   *   XQueryTree() and update xserver_stack.
+   *
+   * - Apply all operations in unverified_predictions to
+   *   verified_stack so we have a predicted stack including Wayland
+   *   windows and free the queue of unverified_predictions.
+   *
+   * - Iterate through the x windows listed in verified_stack at the
+   *   same time as iterating the windows in xserver_list. (Stop
+   *   when we reach the end of the xserver_list)
+   *     - If the window found doesn't match the window expected
+   *     according to the order of xserver_list then:
+   *       - Look ahead for the window we were expecting and restack
+   *       that above the previous X window. If we fail to find the
+   *       expected window then create a new entry for it and stack
+   *       that.
+   *
+   * - Continue to iterate through verified_stack for any remaining
+   *   X windows that we now know aren't in the xserver_list and
+   *   remove them.
+   *
+   * - Free ->predicted_stack if any.
+   */
+
+  meta_topic (META_DEBUG_STACK, "Fully re-synchronizing X stack with verified stack\n");
+
+  requery_xserver_stack (tracker);
+
+  for (l = tracker->unverified_predictions->head; l; l = l->next)
+    meta_stack_op_apply (l->data, tracker->verified_stack);
+  g_queue_clear (tracker->unverified_predictions);
+
+  j = 0;
+  expected_xwindow =
+    &g_array_index (tracker->xserver_stack, MetaStackWindow, j);
+
+  for (i = 0;
+       i < tracker->verified_stack->len;
+       )
+    {
+      MetaStackWindow *current =
+        &g_array_index (tracker->verified_stack, MetaStackWindow, i);
+
+      if (current->any.type != META_WINDOW_CLIENT_TYPE_X11)
+        {
+          /* Progress i but not j */
+          i++;
+          continue;
+        }
+
+      if (current->x11.xwindow != expected_xwindow->x11.xwindow)
+        {
+          MetaStackWindow new;
+          MetaStackWindow *expected;
+          int expected_index;
+          
+          /* If the current window corresponds to a window that's not
+           * in xserver_stack any more then the least disruptive thing
+           * we can do is to simply remove it and take another look at
+           * the same index.
+           *
+           * Note: we didn't used to do this and instead relied on
+           * removed windows getting pushed to the end of the list so
+           * they could all be removed together but this also resulted
+           * in pushing Wayland windows to the end too, disrupting
+           * their positioning relative to X windows too much.
+           *
+           * Technically we only need to look forward from j if we
+           * wanted to optimize this a bit...
+           */
+          if (find_window (tracker->xserver_stack, current) < 0)
+            {
+              g_array_remove_index (tracker->verified_stack, i);
+              continue;
+            }
+
+          /* Technically we only need to look forward from i if we
+           * wanted to optimize this a bit... */
+          expected_index =
+            find_window (tracker->verified_stack, expected_xwindow);
+
+          if (expected_index >= 0)
+            {
+              expected = &g_array_index (tracker->verified_stack,
+                                         MetaStackWindow, expected_index);
+            }
+          else
+            {
+              new.any.type = META_WINDOW_CLIENT_TYPE_X11;
+              new.x11.xwindow = expected_xwindow->x11.xwindow;
+
+              g_array_append_val (tracker->verified_stack, new);
+
+              expected = &new;
+              expected_index = tracker->verified_stack->len - 1;
+            }
+
+          /* Note: that this move will effectively bump the index of
+           * the current window.
+           *
+           * We want to continue by re-checking this window against
+           * the next expected window though so we don't have to
+           * update i to compensate here.
+           */
+          move_window_above (tracker->verified_stack, expected,
+                             expected_index, /* current index */
+                             i - 1); /* above */
+          modified_stack = TRUE;
+        }
+
+      /* NB: we want to make sure that if we break the loop because j
+       * reaches the end of xserver_stack that i has also been
+       * incremented already so that we can run a final loop to remove
+       * remaining windows based on the i index. */
+      i++;
+
+      j++;
+      expected_xwindow =
+        &g_array_index (tracker->xserver_stack, MetaStackWindow, j);
+
+      if (j >= tracker->xserver_stack->len)
+        break;
+    }
+
+  /* We now know that any remaining X windows aren't listed in the
+   * xserver_stack and so we can remove them. */
+  while (i < tracker->verified_stack->len)
+    {
+      MetaStackWindow *current =
+        &g_array_index (tracker->verified_stack, MetaStackWindow, i);
+
+      if (current->any.type == META_WINDOW_CLIENT_TYPE_X11)
+        g_array_remove_index (tracker->verified_stack, i);
+      else
+        i++;
+
+      modified_stack = TRUE;
+    }
+
+  /* If we get to the end of verified_list and there are any remaining
+   * entries in xserver_list then append them all to the end */
+  for (; j < tracker->xserver_stack->len; j++)
+    {
+      MetaStackWindow *current =
+        &g_array_index (tracker->xserver_stack, MetaStackWindow, j);
+      g_array_append_val (tracker->verified_stack, *current);
+
+      modified_stack = TRUE;
+    }
+
+  if (modified_stack)
     {
       if (tracker->predicted_stack)
         {
@@ -556,6 +1029,48 @@ stack_tracker_event_received (MetaStackTracker *tracker,
       meta_stack_tracker_queue_sync_stack (tracker);
     }
 
+  return modified_stack;
+}
+
+static void
+stack_tracker_event_received (MetaStackTracker *tracker,
+			      MetaStackOp      *op)
+{
+  gboolean need_sync = FALSE;
+  gboolean verified;
+
+  meta_stack_op_dump (op, "Stack op event received: ", "\n");
+
+  if (op->any.serial < tracker->xserver_serial)
+    {
+      g_warning ("Spurious X event received affecting stack; doing full re-query");
+      resync_verified_stack_with_xserver_stack (tracker);
+      meta_stack_tracker_dump (tracker);
+      return;
+    }
+
+  tracker->xserver_serial = op->any.serial;
+
+#warning "TODO: remove unused tracker->xserver_stack"
+  /* XXX: With the design we have ended up with it looks like we've
+   * ended up making it unnecessary to maintain tracker->xserver_stack
+   * since we only need an xserver_stack during the
+   * resync_verified_stack_with_xserver_stack() at which point we are
+   * going to query the full stack from the X server using
+   * XQueryTree() anyway.
+   *
+   * TODO: remove tracker->xserver_stack.
+   */
+  meta_stack_op_apply (op, tracker->xserver_stack);
+
+  verified = stack_tracker_verify_predictions (tracker, op, &need_sync);
+  if (!verified)
+    {
+      resync_verified_stack_with_xserver_stack (tracker);
+      meta_stack_tracker_dump (tracker);
+      return;
+    }
+
   meta_stack_tracker_dump (tracker);
 }
 
@@ -567,7 +1082,8 @@ meta_stack_tracker_create_event (MetaStackTracker    *tracker,
 
   op.any.type = STACK_OP_ADD;
   op.any.serial = event->serial;
-  op.add.window = event->window;
+  op.add.window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  op.add.window.x11.xwindow = event->window;
 
   stack_tracker_event_received (tracker, &op);
 }
@@ -580,7 +1096,8 @@ meta_stack_tracker_destroy_event (MetaStackTracker    *tracker,
 
   op.any.type = STACK_OP_REMOVE;
   op.any.serial = event->serial;
-  op.remove.window = event->window;
+  op.remove.window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  op.remove.window.x11.xwindow = event->window;
 
   stack_tracker_event_received (tracker, &op);
 }
@@ -595,7 +1112,8 @@ meta_stack_tracker_reparent_event (MetaStackTracker    *tracker,
 
       op.any.type = STACK_OP_ADD;
       op.any.serial = event->serial;
-      op.add.window = event->window;
+      op.add.window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+      op.add.window.x11.xwindow = event->window;
 
       stack_tracker_event_received (tracker, &op);
     }
@@ -605,7 +1123,8 @@ meta_stack_tracker_reparent_event (MetaStackTracker    *tracker,
 
       op.any.type = STACK_OP_REMOVE;
       op.any.serial = event->serial;
-      op.remove.window = event->window;
+      op.remove.window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+      op.remove.window.x11.xwindow = event->window;
 
       stack_tracker_event_received (tracker, &op);
     }
@@ -619,8 +1138,10 @@ meta_stack_tracker_configure_event (MetaStackTracker    *tracker,
 
   op.any.type = STACK_OP_RAISE_ABOVE;
   op.any.serial = event->serial;
-  op.raise_above.window = event->window;
-  op.raise_above.sibling = event->above;
+  op.raise_above.window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  op.raise_above.window.x11.xwindow = event->window;
+  op.raise_above.sibling.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  op.raise_above.sibling.x11.xwindow = event->above;
 
   stack_tracker_event_received (tracker, &op);
 }
@@ -644,14 +1165,14 @@ meta_stack_tracker_configure_event (MetaStackTracker    *tracker,
  */
 void
 meta_stack_tracker_get_stack (MetaStackTracker *tracker,
-			      Window          **windows,
+                              MetaStackWindow **windows,
 			      int              *n_windows)
 {
   GArray *stack;
 
-  if (tracker->queued_requests->length == 0)
+  if (tracker->unverified_predictions->length == 0)
     {
-      stack = tracker->server_stack;
+      stack = tracker->verified_stack;
     }
   else
     {
@@ -659,9 +1180,8 @@ meta_stack_tracker_get_stack (MetaStackTracker *tracker,
         {
           GList *l;
 
-          tracker->predicted_stack = copy_stack ((Window *)tracker->server_stack->data,
-                                                 tracker->server_stack->len);
-          for (l = tracker->queued_requests->head; l; l = l->next)
+          tracker->predicted_stack = copy_stack (tracker->verified_stack);
+          for (l = tracker->unverified_predictions->head; l; l = l->next)
             {
               MetaStackOp *op = l->data;
               meta_stack_op_apply (op, tracker->predicted_stack);
@@ -671,8 +1191,11 @@ meta_stack_tracker_get_stack (MetaStackTracker *tracker,
       stack = tracker->predicted_stack;
     }
 
+  meta_topic (META_DEBUG_STACK, "Get Stack\n");
+  meta_stack_tracker_dump (tracker);
+
   if (windows)
-    *windows = (Window *)stack->data;
+    *windows = (MetaStackWindow *)stack->data;
   if (n_windows)
     *n_windows = stack->len;
 }
@@ -687,8 +1210,8 @@ meta_stack_tracker_get_stack (MetaStackTracker *tracker,
 void
 meta_stack_tracker_sync_stack (MetaStackTracker *tracker)
 {
+  MetaStackWindow *windows;
   GList *meta_windows;
-  Window *windows;
   int n_windows;
   int i;
 
@@ -703,20 +1226,26 @@ meta_stack_tracker_sync_stack (MetaStackTracker *tracker)
   meta_windows = NULL;
   for (i = 0; i < n_windows; i++)
     {
-      MetaWindow *meta_window;
-
-      meta_window = meta_display_lookup_x_window (tracker->screen->display,
-                                                  windows[i]);
-      /* When mapping back from xwindow to MetaWindow we have to be a bit careful;
-       * children of the root could include unmapped windows created by toolkits
-       * for internal purposes, including ones that we have registered in our
-       * XID => window table. (Wine uses a toplevel for _NET_WM_USER_TIME_WINDOW;
-       * see window-prop.c:reload_net_wm_user_time_window() for registration.)
-       */
-      if (meta_window &&
-          (windows[i] == meta_window->xwindow ||
-           (meta_window->frame && windows[i] == meta_window->frame->xwindow)))
-        meta_windows = g_list_prepend (meta_windows, meta_window);
+      MetaStackWindow *window = &windows[i];
+
+      if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+        {
+          MetaWindow *meta_window =
+            meta_display_lookup_x_window (tracker->screen->display, windows[i].x11.xwindow);
+
+          /* When mapping back from xwindow to MetaWindow we have to be a bit careful;
+           * children of the root could include unmapped windows created by toolkits
+           * for internal purposes, including ones that we have registered in our
+           * XID => window table. (Wine uses a toplevel for _NET_WM_USER_TIME_WINDOW;
+           * see window-prop.c:reload_net_wm_user_time_window() for registration.)
+           */
+          if (meta_window &&
+              (windows[i].x11.xwindow == meta_window->xwindow ||
+               (meta_window->frame && windows[i].x11.xwindow == meta_window->frame->xwindow)))
+            meta_windows = g_list_prepend (meta_windows, meta_window);
+        }
+      else
+        meta_windows = g_list_prepend (meta_windows, window->wayland.meta_window);
     }
 
   if (tracker->screen->display->compositor)
diff --git a/src/core/stack-tracker.h b/src/core/stack-tracker.h
index cb12dcd00..4b7b1bfd7 100644
--- a/src/core/stack-tracker.h
+++ b/src/core/stack-tracker.h
@@ -37,36 +37,55 @@
 #define META_STACK_TRACKER_H
 
 #include <meta/screen.h>
+#include <meta/window.h>
 
 typedef struct _MetaStackTracker MetaStackTracker;
 
+typedef union _MetaStackWindow
+{
+  struct {
+    MetaWindowClientType type;
+  } any;
+  struct {
+    MetaWindowClientType type;
+    Window xwindow;
+  } x11;
+  struct {
+    MetaWindowClientType type;
+    MetaWindow *meta_window;
+  } wayland;
+} MetaStackWindow;
+
+gboolean meta_stack_window_equal (const MetaStackWindow *a,
+                                  const MetaStackWindow *b);
+
 MetaStackTracker *meta_stack_tracker_new  (MetaScreen       *screen);
 void              meta_stack_tracker_free (MetaStackTracker *tracker);
 
 /* These functions are called when we make an X call that changes the
  * stacking order; this allows MetaStackTracker to predict stacking
  * order before it receives events back from the X server */
-void meta_stack_tracker_record_add             (MetaStackTracker *tracker,
-						Window            window,
-                                                gulong            serial);
-void meta_stack_tracker_record_remove          (MetaStackTracker *tracker,
-						Window            window,
-                                                gulong            serial);
-void meta_stack_tracker_record_restack_windows (MetaStackTracker *tracker,
-						Window           *windows,
-						int               n_windows,
-                                                gulong            serial);
-void meta_stack_tracker_record_raise_above     (MetaStackTracker *tracker,
-						Window            window,
-						Window            sibling,
-                                                gulong            serial);
-void meta_stack_tracker_record_lower_below    (MetaStackTracker *tracker,
-						Window            window,
-						Window            sibling,
-                                                gulong            serial);
-void meta_stack_tracker_record_lower           (MetaStackTracker *tracker,
-						Window            window,
-                                                gulong            serial);
+void meta_stack_tracker_record_add             (MetaStackTracker      *tracker,
+                                                const MetaStackWindow *window,
+                                                gulong                 serial);
+void meta_stack_tracker_record_remove          (MetaStackTracker      *tracker,
+                                                const MetaStackWindow *window,
+                                                gulong                 serial);
+void meta_stack_tracker_record_restack_windows (MetaStackTracker      *tracker,
+                                                const MetaStackWindow *windows,
+						int                    n_windows,
+                                                gulong                 serial);
+void meta_stack_tracker_record_raise_above     (MetaStackTracker      *tracker,
+                                                const MetaStackWindow *window,
+                                                const MetaStackWindow *sibling,
+                                                gulong                 serial);
+void meta_stack_tracker_record_lower_below    (MetaStackTracker       *tracker,
+                                               const MetaStackWindow  *window,
+                                               const MetaStackWindow  *sibling,
+                                               gulong                  serial);
+void meta_stack_tracker_record_lower           (MetaStackTracker      *tracker,
+                                                const MetaStackWindow *window,
+                                                gulong                 serial);
 
 /* These functions are used to update the stack when we get events
  * reflecting changes to the stacking order */
@@ -79,9 +98,9 @@ void meta_stack_tracker_reparent_event  (MetaStackTracker    *tracker,
 void meta_stack_tracker_configure_event (MetaStackTracker    *tracker,
 					 XConfigureEvent     *event);
 
-void meta_stack_tracker_get_stack  (MetaStackTracker  *tracker,
-                                    Window           **windows,
-                                    int               *n_windows);
+void meta_stack_tracker_get_stack  (MetaStackTracker      *tracker,
+                                    MetaStackWindow      **windows,
+                                    int                   *n_entries);
 
 void meta_stack_tracker_sync_stack       (MetaStackTracker *tracker);
 void meta_stack_tracker_queue_sync_stack (MetaStackTracker *tracker);
diff --git a/src/core/stack.c b/src/core/stack.c
index 3b05cdbd3..85b0f35dd 100644
--- a/src/core/stack.c
+++ b/src/core/stack.c
@@ -52,7 +52,7 @@
 
 #define WINDOW_IN_STACK(w) (w->stack_position >= 0)
 
-static void stack_sync_to_server (MetaStack *stack);
+static void stack_sync_to_xserver (MetaStack *stack);
 static void meta_window_set_stack_position_no_sync (MetaWindow *window,
                                                     int         position);
 static void stack_do_window_deletions (MetaStack *stack);
@@ -71,14 +71,14 @@ meta_stack_new (MetaScreen *screen)
   stack = g_new (MetaStack, 1);
 
   stack->screen = screen;
-  stack->windows = g_array_new (FALSE, FALSE, sizeof (Window));
+  stack->xwindows = g_array_new (FALSE, FALSE, sizeof (Window));
 
   stack->sorted = NULL;
   stack->added = NULL;
   stack->removed = NULL;
 
   stack->freeze_count = 0;
-  stack->last_root_children_stacked = NULL;
+  stack->last_all_root_children_stacked = NULL;
 
   stack->n_positions = 0;
 
@@ -89,17 +89,34 @@ meta_stack_new (MetaScreen *screen)
   return stack;
 }
 
+static void
+free_last_all_root_children_stacked_cache (MetaStack *stack)
+{
+  unsigned int i;
+
+  for (i = 0; i < stack->last_all_root_children_stacked->len; i++)
+    {
+      MetaStackWindow *window = &g_array_index (stack->last_all_root_children_stacked, MetaStackWindow, i);
+      if (window->any.type == META_WINDOW_CLIENT_TYPE_WAYLAND)
+        g_object_remove_weak_pointer (G_OBJECT (window->wayland.meta_window),
+                                      (gpointer *)&window->wayland.meta_window);
+    }
+
+  g_array_free (stack->last_all_root_children_stacked, TRUE);
+  stack->last_all_root_children_stacked = NULL;
+}
+
 void
 meta_stack_free (MetaStack *stack)
 {
-  g_array_free (stack->windows, TRUE);
+  g_array_free (stack->xwindows, TRUE);
 
   g_list_free (stack->sorted);
   g_list_free (stack->added);
   g_list_free (stack->removed);
 
-  if (stack->last_root_children_stacked)
-    g_array_free (stack->last_root_children_stacked, TRUE);
+  if (stack->last_all_root_children_stacked)
+    free_last_all_root_children_stacked_cache (stack);
   
   g_free (stack);
 }
@@ -121,7 +138,7 @@ meta_stack_add (MetaStack  *stack,
               "Window %s has stack_position initialized to %d\n",
               window->desc, window->stack_position);
   
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -157,7 +174,7 @@ meta_stack_remove (MetaStack  *stack,
     stack->removed = g_list_prepend (stack->removed,
                                      GUINT_TO_POINTER (window->frame->xwindow));
   
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -167,7 +184,7 @@ meta_stack_update_layer (MetaStack  *stack,
 {
   stack->need_relayer = TRUE;
   
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -177,7 +194,7 @@ meta_stack_update_transient (MetaStack  *stack,
 {
   stack->need_constrain = TRUE;
   
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -206,7 +223,7 @@ meta_stack_raise (MetaStack  *stack,
 
   meta_window_set_stack_position_no_sync (window, max_stack_position);
 
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -234,7 +251,7 @@ meta_stack_lower (MetaStack  *stack,
 
   meta_window_set_stack_position_no_sync (window, min_stack_position);
   
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, window->screen->active_workspace);
 }
 
@@ -250,7 +267,7 @@ meta_stack_thaw (MetaStack *stack)
   g_return_if_fail (stack->freeze_count > 0);
   
   stack->freeze_count -= 1;
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, NULL);
 }
 
@@ -829,7 +846,7 @@ stack_do_window_deletions (MetaStack *stack)
       /* We go from the end figuring removals are more
        * likely to be recent.
        */
-      i = stack->windows->len;
+      i = stack->xwindows->len;
       while (i > 0)
         {
           --i;
@@ -840,9 +857,9 @@ stack_do_window_deletions (MetaStack *stack)
            * both the window->xwindow and window->frame->xwindow
            * in the removal list.
            */
-          if (xwindow == g_array_index (stack->windows, Window, i))
+          if (xwindow == g_array_index (stack->xwindows, Window, i))
             {
-              g_array_remove_index (stack->windows, i);
+              g_array_remove_index (stack->xwindows, i);
               goto next;
             }
         }
@@ -871,10 +888,10 @@ stack_do_window_additions (MetaStack *stack)
                   "Adding %d windows to sorted list\n",
                   n_added);
       
-      old_size = stack->windows->len;
-      g_array_set_size (stack->windows, old_size + n_added);
+      old_size = stack->xwindows->len;
+      g_array_set_size (stack->xwindows, old_size + n_added);
       
-      end = &g_array_index (stack->windows, Window, old_size);
+      end = &g_array_index (stack->xwindows, Window, old_size);
 
       /* stack->added has the most recent additions at the
        * front of the list, so we need to reverse it
@@ -1029,6 +1046,102 @@ stack_ensure_sorted (MetaStack *stack)
   stack_do_resort (stack);
 }
 
+static MetaStackWindow *
+find_top_most_managed_window (MetaScreen *screen,
+                              const MetaStackWindow *ignore)
+{
+  MetaStackTracker *stack_tracker = screen->stack_tracker;
+  MetaStackWindow *windows;
+  int n_windows;
+  int i;
+
+  meta_stack_tracker_get_stack (stack_tracker,
+                                &windows, &n_windows);
+
+  /* Children are in order from bottom to top. We want to
+   * find the topmost managed child, then configure
+   * our window to be above it.
+   */
+  for (i = n_windows -1; i >= 0; i--)
+    {
+      MetaStackWindow *other_window = &windows[i];
+
+      if (other_window->any.type == ignore->any.type &&
+          ((other_window->any.type == META_WINDOW_CLIENT_TYPE_X11 &&
+            other_window->x11.xwindow == ignore->x11.xwindow) ||
+           other_window->wayland.meta_window == ignore->wayland.meta_window))
+        {
+          /* Do nothing. This means we're already the topmost managed
+           * window, but it DOES NOT mean we are already just above
+           * the topmost managed window. This is important because if
+           * an override redirect window is up, and we map a new
+           * managed window, the new window is probably above the old
+           * popup by default, and we want to push it below that
+           * popup. So keep looking for a sibling managed window
+           * to be moved below.
+           */
+        }
+      else
+        {
+          if (other_window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+            {
+              MetaWindow *other = meta_display_lookup_x_window (screen->display,
+                                                                other_window->x11.xwindow);
+
+              if (other != NULL && !other->override_redirect)
+                return other_window;
+            }
+          else
+            {
+              /* All wayland windows are currently considered "managed"
+               * TODO: consider wayland pop-up windows like override
+               * redirect windows here. */
+              return other_window;
+            }
+        }
+    }
+
+  return NULL;
+}
+
+/* When moving an X window we sometimes need an X based sibling.
+ *
+ * If the given sibling is X based this function returns it back
+ * otherwise it searches downwards looking for the nearest X window.
+ *
+ * If no X based sibling could be found return NULL. */
+static MetaStackWindow *
+find_x11_sibling_downwards (MetaScreen *screen,
+                            MetaStackWindow *sibling)
+{
+  MetaStackTracker *stack_tracker = screen->stack_tracker;
+  MetaStackWindow *windows;
+  int n_windows;
+  int i;
+
+  if (sibling->any.type == META_WINDOW_CLIENT_TYPE_X11)
+    return sibling;
+
+  meta_stack_tracker_get_stack (stack_tracker,
+                                &windows, &n_windows);
+
+  /* NB: Children are in order from bottom to top and we
+   * want to search downwards for the nearest X window.
+   */
+
+  for (i = n_windows - 1; i >= 0; i--)
+    if (meta_stack_window_equal (&windows[i], sibling))
+      break;
+
+  for (; i >= 0; i--)
+    {
+      if (windows[i].any.type == META_WINDOW_CLIENT_TYPE_X11)
+        return &windows[i];
+    }
+
+  return NULL;
+}
+
 /**
  * raise_window_relative_to_managed_windows:
  *
@@ -1053,84 +1166,74 @@ stack_ensure_sorted (MetaStack *stack)
  */
 static void
 raise_window_relative_to_managed_windows (MetaScreen *screen,
-                                          Window      xwindow)
+                                          const MetaStackWindow *window)
 {
+  gulong serial = 0;
+  MetaStackWindow *sibling;
 
-  Window *children;
-  int n_children;
-  int i;
-
-  meta_stack_tracker_get_stack (screen->stack_tracker,
-                                &children, &n_children);
-
-  /* Children are in order from bottom to top. We want to
-   * find the topmost managed child, then configure
-   * our window to be above it.
-   */
-  i = n_children - 1;
-  while (i >= 0)
+  sibling = find_top_most_managed_window (screen, window);
+  if (!sibling)
     {
-      if (children[i] == xwindow)
+      if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
         {
-          /* Do nothing. This means we're already the topmost managed
-           * window, but it DOES NOT mean we are already just above
-           * the topmost managed window. This is important because if
-           * an override redirect window is up, and we map a new
-           * managed window, the new window is probably above the old
-           * popup by default, and we want to push it below that
-           * popup. So keep looking for a sibling managed window
-           * to be moved below.
+          serial = XNextRequest (screen->display->xdisplay);
+          meta_error_trap_push (screen->display);
+          XLowerWindow (screen->display->xdisplay,
+                        window->x11.xwindow);
+          meta_error_trap_pop (screen->display);
+        }
+
+      /* No sibling to use, just lower ourselves to the bottom
+       * to be sure we're below any override redirect windows.
            */
+      meta_stack_tracker_record_lower (screen->stack_tracker,
+                                       window,
+                                       serial);
+      return;
         }
-      else
-        {
-          MetaWindow *other = meta_display_lookup_x_window (screen->display,
-                                                            children[i]);
-          if (other != NULL && !other->override_redirect)
-            {
-              XWindowChanges changes;
 
-              /* children[i] is the topmost managed child */
+  /* window is the topmost managed child */
               meta_topic (META_DEBUG_STACK,
                           "Moving 0x%lx above topmost managed child window 0x%lx\n",
-                          xwindow, children[i]);
+              window->any.type == META_WINDOW_CLIENT_TYPE_X11 ? window->x11.xwindow: 0,
+              sibling->any.type == META_WINDOW_CLIENT_TYPE_X11 ? sibling->x11.xwindow: 0);
+
+  if (window->any.type == META_WINDOW_CLIENT_TYPE_X11)
+    {
+      XWindowChanges changes;
+      MetaStackWindow *x11_sibling = find_x11_sibling_downwards (screen, sibling);
+      serial = XNextRequest (screen->display->xdisplay);
 
-              changes.sibling = children[i];
+      if (x11_sibling)
+        {
+          changes.sibling = x11_sibling->x11.xwindow;
               changes.stack_mode = Above;
 
               meta_error_trap_push (screen->display);
-              meta_stack_tracker_record_raise_above (screen->stack_tracker,
-                                                     xwindow,
-                                                     children[i],
-                                                     XNextRequest (screen->display->xdisplay));
               XConfigureWindow (screen->display->xdisplay,
-                                xwindow,
+                            window->x11.xwindow,
                                 CWSibling | CWStackMode,
                                 &changes);
               meta_error_trap_pop (screen->display);
-
-              break;
-            }
         }
-
-      --i;
-    }
-
-  if (i < 0)
+      else
     {
       /* No sibling to use, just lower ourselves to the bottom
        * to be sure we're below any override redirect windows.
        */
       meta_error_trap_push (screen->display);
-      meta_stack_tracker_record_lower (screen->stack_tracker,
-                                       xwindow,
-                                       XNextRequest (screen->display->xdisplay));
       XLowerWindow (screen->display->xdisplay,
-                    xwindow);
+                        window->x11.xwindow);
       meta_error_trap_pop (screen->display);
     }
 }
 
+  meta_stack_tracker_record_raise_above (screen->stack_tracker,
+                                         window,
+                                         sibling,
+                                         serial);
+}
+
 /**
  * stack_sync_to_server:
  *
@@ -1145,13 +1248,16 @@ raise_window_relative_to_managed_windows (MetaScreen *screen,
  * job of computing the minimal set of stacking requests needed.
  */
 static void
-stack_sync_to_server (MetaStack *stack)
+stack_sync_to_xserver (MetaStack *stack)
 {
-  GArray *stacked;
-  GArray *root_children_stacked;
+  GArray *x11_stacked;
+  GArray *x11_root_children_stacked;
+  GArray *all_root_children_stacked; /* wayland OR x11 */
   GList *tmp;
-  GArray *all_hidden;
+  GArray *x11_hidden;
+  GArray *x11_hidden_stack_windows;
   int n_override_redirect = 0;
+  MetaStackWindow guard_stack_window;
   
   /* Bail out if frozen */
   if (stack->freeze_count > 0)
@@ -1166,13 +1272,17 @@ stack_sync_to_server (MetaStack *stack)
    * _NET hints, and "root_children_stacked" is in top-to-bottom
    * order for XRestackWindows()
    */
-  stacked = g_array_new (FALSE, FALSE, sizeof (Window));
-  root_children_stacked = g_array_new (FALSE, FALSE, sizeof (Window));
-  all_hidden = g_array_new (FALSE, FALSE, sizeof (Window));
+  x11_stacked = g_array_new (FALSE, FALSE, sizeof (Window));
+
+  all_root_children_stacked = g_array_new (FALSE, FALSE, sizeof (MetaStackWindow));
+  x11_root_children_stacked = g_array_new (FALSE, FALSE, sizeof (Window));
+
+  x11_hidden_stack_windows = g_array_new (FALSE, FALSE, sizeof (MetaStackWindow));
+  x11_hidden = g_array_new (FALSE, FALSE, sizeof (Window));
 
   /* The screen guard window sits above all hidden windows and acts as
    * a barrier to input reaching these windows. */
-  g_array_append_val (all_hidden, stack->screen->guard_window);
+  g_array_append_val (x11_hidden, stack->screen->guard_window);
 
   meta_topic (META_DEBUG_STACK, "Top to bottom: ");
   meta_push_no_msg_prefix ();
@@ -1181,6 +1291,9 @@ stack_sync_to_server (MetaStack *stack)
     {
       MetaWindow *w = tmp->data;
       Window top_level_window;
+      MetaStackWindow stack_window;
+
+      stack_window.any.type = w->client_type;
       
       meta_topic (META_DEBUG_STACK, "%u:%d - %s ",
 		  w->layer, w->stack_position, w->desc);
@@ -1189,60 +1302,93 @@ stack_sync_to_server (MetaStack *stack)
       if (w->override_redirect)
 	n_override_redirect++;
       else
-	g_array_prepend_val (stacked, w->xwindow);
+	g_array_prepend_val (x11_stacked, w->xwindow);
       
       if (w->frame)
 	top_level_window = w->frame->xwindow;
       else
 	top_level_window = w->xwindow;
 
+      if (w->client_type == META_WINDOW_CLIENT_TYPE_X11)
+        stack_window.x11.xwindow = top_level_window;
+      else
+        stack_window.wayland.meta_window = w;
+
       /* We don't restack hidden windows along with the rest, though they are
        * reflected in the _NET hints. Hidden windows all get pushed below
        * the screens fullscreen guard_window. */
       if (w->hidden)
 	{
-	  g_array_append_val (all_hidden, top_level_window);
+          if (w->client_type == META_WINDOW_CLIENT_TYPE_X11)
+            {
+              MetaStackWindow stack_window;
+
+              stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+              stack_window.x11.xwindow = top_level_window;
+
+              g_array_append_val (x11_hidden_stack_windows, stack_window);
+              g_array_append_val (x11_hidden, top_level_window);
+            }
 	  continue;
 	}
 
+      g_array_append_val (all_root_children_stacked, stack_window);
+
       /* build XRestackWindows() array from top to bottom */
-      g_array_append_val (root_children_stacked, top_level_window);
+      if (w->client_type == META_WINDOW_CLIENT_TYPE_X11)
+        g_array_append_val (x11_root_children_stacked, top_level_window);
+      else
+        {
+          MetaStackWindow *new;
+
+          /* So we can determine later if a cached stack window is
+           * stale because the corresponding window has been freed we
+           * associate a weak pointer with the new window. */
+          new = &g_array_index (all_root_children_stacked, MetaStackWindow, all_root_children_stacked->len - 1);
+          g_object_add_weak_pointer (G_OBJECT (new->wayland.meta_window),
+                                     (gpointer *)&new->wayland.meta_window);
+        }
     }
 
   meta_topic (META_DEBUG_STACK, "\n");
   meta_pop_no_msg_prefix ();
 
-  /* All windows should be in some stacking order */
-  if (stacked->len != stack->windows->len - n_override_redirect)
+  /* All X windows should be in some stacking order */
+  if (x11_stacked->len != stack->xwindows->len - n_override_redirect)
     meta_bug ("%u windows stacked, %u windows exist in stack\n",
-              stacked->len, stack->windows->len);
+              x11_stacked->len, stack->xwindows->len);
   
   /* Sync to server */
 
   meta_topic (META_DEBUG_STACK, "Restacking %u windows\n",
-              root_children_stacked->len);
+              all_root_children_stacked->len);
   
   meta_error_trap_push (stack->screen->display);
 
-  if (stack->last_root_children_stacked == NULL)
+  if (stack->last_all_root_children_stacked == NULL)
     {
       /* Just impose our stack, we don't know the previous state.
        * This involves a ton of circulate requests and may flicker.
        */
       meta_topic (META_DEBUG_STACK, "Don't know last stack state, restacking everything\n");
 
-      if (root_children_stacked->len > 0)
+      if (all_root_children_stacked->len > 1)
         {
-          meta_stack_tracker_record_restack_windows (stack->screen->stack_tracker,
-                                                     (Window *) root_children_stacked->data,
-                                                     root_children_stacked->len,
-                                                     XNextRequest (stack->screen->display->xdisplay));
+          gulong serial = 0;
+          if (x11_root_children_stacked->len > 1)
+            {
+              serial = XNextRequest (stack->screen->display->xdisplay);
           XRestackWindows (stack->screen->display->xdisplay,
-                           (Window *) root_children_stacked->data,
-                           root_children_stacked->len);
+                               (Window *) x11_root_children_stacked->data,
+                               x11_root_children_stacked->len);
+            }
+          meta_stack_tracker_record_restack_windows (stack->screen->stack_tracker,
+                                                     (MetaStackWindow *) all_root_children_stacked->data,
+                                                     all_root_children_stacked->len,
+                                                     serial);
         }
     }
-  else if (root_children_stacked->len > 0)
+  else if (all_root_children_stacked->len > 0)
     {
       /* Try to do minimal window moves to get the stack in order */
       /* A point of note: these arrays include frames not client windows,
@@ -1250,28 +1396,34 @@ stack_sync_to_server (MetaStack *stack)
        * was saved, then we may have inefficiency, but I don't think things
        * break...
        */
-      const Window *old_stack = (Window *) stack->last_root_children_stacked->data;
-      const Window *new_stack = (Window *) root_children_stacked->data;
-      const int old_len = stack->last_root_children_stacked->len;
-      const int new_len = root_children_stacked->len;
-      const Window *oldp = old_stack;
-      const Window *newp = new_stack;
-      const Window *old_end = old_stack + old_len;
-      const Window *new_end = new_stack + new_len;
-      Window last_window = None;
-      
+      const MetaStackWindow *old_stack = (MetaStackWindow *) stack->last_all_root_children_stacked->data;
+      const MetaStackWindow *new_stack = (MetaStackWindow *) all_root_children_stacked->data;
+      const int old_len = stack->last_all_root_children_stacked->len;
+      const int new_len = all_root_children_stacked->len;
+      const MetaStackWindow *oldp = old_stack;
+      const MetaStackWindow *newp = new_stack;
+      const MetaStackWindow *old_end = old_stack + old_len;
+      const MetaStackWindow *new_end = new_stack + new_len;
+      Window last_xwindow = None;
+      const MetaStackWindow *last_window = NULL;
+
       while (oldp != old_end &&
              newp != new_end)
         {
-          if (*oldp == *newp)
+          if (meta_stack_window_equal (oldp, newp))
             {
               /* Stacks are the same here, move on */
               ++oldp;
-              last_window = *newp;
+              if (newp->any.type == META_WINDOW_CLIENT_TYPE_X11)
+                last_xwindow = newp->x11.xwindow;
+              last_window = newp;
               ++newp;
             }
-          else if (meta_display_lookup_x_window (stack->screen->display,
-                                                 *oldp) == NULL)
+          else if ((oldp->any.type == META_WINDOW_CLIENT_TYPE_X11 &&
+                    meta_display_lookup_x_window (stack->screen->display,
+                                                  oldp->x11.xwindow) == NULL) ||
+                   (oldp->any.type == META_WINDOW_CLIENT_TYPE_WAYLAND &&
+                    oldp->wayland.meta_window == NULL))
             {
               /* *oldp is no longer known to us (probably destroyed),
                * so we can just skip it
@@ -1280,75 +1432,161 @@ stack_sync_to_server (MetaStack *stack)
             }
           else
             {
-              /* Move *newp below last_window */
-              if (last_window == None)
+              /* Move *newp below the last_window */
+              if (!last_window)
+                {
+                  meta_topic (META_DEBUG_STACK, "Using window 0x%lx as topmost (but leaving it in-place)\n",
+                              newp->x11.xwindow);
+
+                  raise_window_relative_to_managed_windows (stack->screen, newp);
+                }
+              else if (newp->any.type == META_WINDOW_CLIENT_TYPE_X11 &&
+                       last_xwindow == None)
                 {
-                  meta_topic (META_DEBUG_STACK, "Using window 0x%lx as topmost (but leaving it in-place)\n", *newp);
+                  /* In this case we have an X window that we need to
+                   * put below a wayland window and this is the
+                   * topmost X window. */
+                  
+                  /* In X terms (because this is the topmost X window)
+                   * we want to
+                   * raise_window_relative_to_managed_windows() to
+                   * ensure the X window is below override-redirect
+                   * pop-up windows.
+                   *
+                   * In Wayland terms we just want to ensure
+                   * newp is lowered below last_window (which
+                   * notably doesn't require an X request because we
+                   * know last_window isn't an X window).
+                   */
+
+                  raise_window_relative_to_managed_windows (stack->screen, newp);
 
-                  raise_window_relative_to_managed_windows (stack->screen,
-                                                            *newp);
+                  meta_stack_tracker_record_lower_below (stack->screen->stack_tracker,
+                                                         newp, last_window,
+                                                         0); /* no x request serial */
                 }
               else
                 {
-                  /* This means that if last_window is dead, but not
+                  gulong serial = 0;
+
+                  /* This means that if last_xwindow is dead, but not
                    * *newp, then we fail to restack *newp; but on
-                   * unmanaging last_window, we'll fix it up.
+                   * unmanaging last_xwindow, we'll fix it up.
                    */
                   
+                  meta_topic (META_DEBUG_STACK, "Placing window 0x%lx below 0x%lx\n",
+                              newp->any.type == META_WINDOW_CLIENT_TYPE_X11 ? newp->x11.xwindow : 0,
+                              last_xwindow);
+
+                  if (newp->any.type == META_WINDOW_CLIENT_TYPE_X11)
+                    {
                   XWindowChanges changes;
+                      serial = XNextRequest (stack->screen->display->xdisplay);
 
-                  changes.sibling = last_window;
+                      changes.sibling = last_xwindow;
                   changes.stack_mode = Below;
 
-                  meta_topic (META_DEBUG_STACK, "Placing window 0x%lx below 0x%lx\n",
-                              *newp, last_window);
-
-                  meta_stack_tracker_record_lower_below (stack->screen->stack_tracker,
-                                                         *newp, last_window,
-                                                         XNextRequest (stack->screen->display->xdisplay));
                   XConfigureWindow (stack->screen->display->xdisplay,
-                                    *newp,
+                                        newp->x11.xwindow,
                                     CWSibling | CWStackMode,
                                     &changes);
                 }
 
-              last_window = *newp;
+                  meta_stack_tracker_record_lower_below (stack->screen->stack_tracker,
+                                                         newp, last_window,
+                                                         serial);
+                }
+
+              if (newp->any.type == META_WINDOW_CLIENT_TYPE_X11)
+                last_xwindow = newp->x11.xwindow;
+              last_window = newp;
               ++newp;
             }
         }
 
       if (newp != new_end)
         {
+          const MetaStackWindow *x_ref;
+          unsigned long serial = 0;
+
           /* Restack remaining windows */
           meta_topic (META_DEBUG_STACK, "Restacking remaining %d windows\n",
                         (int) (new_end - newp));
+
+          /* rewind until we find the last stacked X window that we can use
+           * as a reference point for re-stacking remaining X windows */
+          if (newp != new_stack)
+            for (x_ref = newp - 1;
+                 x_ref->any.type != META_WINDOW_CLIENT_TYPE_X11 && x_ref > new_stack;
+                 x_ref--)
+              ;
+          else
+            x_ref = new_stack;
+
+          /* If we didn't find an X window looking backwards then walk forwards
+           * through the remaining windows to find the first remaining X window
+           * instead. */
+          if (x_ref->any.type != META_WINDOW_CLIENT_TYPE_X11)
+            {
+              for (x_ref = newp;
+                   x_ref->any.type != META_WINDOW_CLIENT_TYPE_X11 && x_ref > new_stack;
+                   x_ref++)
+                ;
+            }
+
+          /* If there are any X windows remaining unstacked then restack them */
+          if (x_ref->any.type == META_WINDOW_CLIENT_TYPE_X11)
+            {
+              int i;
+
+              for (i = x11_root_children_stacked->len - 1; i; i--)
+                {
+                  Window *reference = &g_array_index (x11_root_children_stacked, Window, i);
+
+                  if (*reference == x_ref->x11.xwindow)
+                    {
+                      int n = x11_root_children_stacked->len - i;
+
+                      /* There's no point restacking if there's only one X window */
+                      if (n == 1)
+                        break;
+
+                      serial = XNextRequest (stack->screen->display->xdisplay);
+                      XRestackWindows (stack->screen->display->xdisplay,
+                                       reference, n);
+                      break;
+                    }
+                }
+            }
+
           /* We need to include an already-stacked window
            * in the restack call, so we get in the proper position
            * with respect to it.
            */
           if (newp != new_stack)
-            --newp;
+            newp = MIN (newp - 1, x_ref);
           meta_stack_tracker_record_restack_windows (stack->screen->stack_tracker,
-                                                     (Window *) newp, new_end - newp,
-                                                     XNextRequest (stack->screen->display->xdisplay));
-          XRestackWindows (stack->screen->display->xdisplay,
-                           (Window *) newp, new_end - newp);
+                                                     newp, new_end - newp,
+                                                     serial);
         }
     }
 
-  /* Push hidden windows to the bottom of the stack under the guard window */
+  /* Push hidden X windows to the bottom of the stack under the guard window */
+  guard_stack_window.any.type = META_WINDOW_CLIENT_TYPE_X11;
+  guard_stack_window.x11.xwindow = stack->screen->guard_window;
   meta_stack_tracker_record_lower (stack->screen->stack_tracker,
-                                   stack->screen->guard_window,
+                                   &guard_stack_window,
                                    XNextRequest (stack->screen->display->xdisplay));
   XLowerWindow (stack->screen->display->xdisplay, stack->screen->guard_window);
   meta_stack_tracker_record_restack_windows (stack->screen->stack_tracker,
-                                             (Window *)all_hidden->data,
-                                             all_hidden->len,
+                                             (MetaStackWindow *)x11_hidden_stack_windows->data,
+                                             x11_hidden_stack_windows->len,
                                              XNextRequest (stack->screen->display->xdisplay));
   XRestackWindows (stack->screen->display->xdisplay,
-		   (Window *)all_hidden->data,
-		   all_hidden->len);
-  g_array_free (all_hidden, TRUE);
+		   (Window *)x11_hidden->data,
+		   x11_hidden->len);
+  g_array_free (x11_hidden, TRUE);
+  g_array_free (x11_hidden_stack_windows, TRUE);
 
   meta_error_trap_pop (stack->screen->display);
   /* on error, a window was destroyed; it should eventually
@@ -1363,21 +1601,23 @@ stack_sync_to_server (MetaStack *stack)
                    stack->screen->display->atom__NET_CLIENT_LIST,
                    XA_WINDOW,
                    32, PropModeReplace,
-                   (unsigned char *)stack->windows->data,
-                   stack->windows->len);
+                   (unsigned char *)stack->xwindows->data,
+                   stack->xwindows->len);
   XChangeProperty (stack->screen->display->xdisplay,
                    stack->screen->xroot,
                    stack->screen->display->atom__NET_CLIENT_LIST_STACKING,
                    XA_WINDOW,
                    32, PropModeReplace,
-                   (unsigned char *)stacked->data,
-                   stacked->len);
+                   (unsigned char *)x11_stacked->data,
+                   x11_stacked->len);
+
+  g_array_free (x11_stacked, TRUE);
 
-  g_array_free (stacked, TRUE);
+  if (stack->last_all_root_children_stacked)
+    free_last_all_root_children_stacked_cache (stack);
+  stack->last_all_root_children_stacked = all_root_children_stacked;
 
-  if (stack->last_root_children_stacked)
-    g_array_free (stack->last_root_children_stacked, TRUE);
-  stack->last_root_children_stacked = root_children_stacked;
+  g_array_free (x11_root_children_stacked, TRUE);
 
   /* That was scary... */
 }
@@ -1738,7 +1978,7 @@ meta_stack_set_positions (MetaStack *stack,
   meta_topic (META_DEBUG_STACK,
               "Reset the stack positions of (nearly) all windows\n");
 
-  stack_sync_to_server (stack);
+  stack_sync_to_xserver (stack);
   meta_stack_update_window_tile_matches (stack, NULL);
 }
 
@@ -1801,7 +2041,7 @@ meta_window_set_stack_position (MetaWindow *window,
                                 int         position)
 {
   meta_window_set_stack_position_no_sync (window, position);
-  stack_sync_to_server (window->screen->stack);
+  stack_sync_to_xserver (window->screen->stack);
   meta_stack_update_window_tile_matches (window->screen->stack,
                                          window->screen->active_workspace);
 }
diff --git a/src/core/stack.h b/src/core/stack.h
index fb54e2df0..423672b32 100644
--- a/src/core/stack.h
+++ b/src/core/stack.h
@@ -60,7 +60,7 @@ struct _MetaStack
    * A sequence of all the Windows (X handles, not MetaWindows) of the windows
    * we manage, sorted in order.  Suitable to be passed into _NET_CLIENT_LIST.
    */
-  GArray *windows;
+  GArray *xwindows;
 
   /** The MetaWindows of the windows we manage, sorted in order. */
   GList *sorted;
@@ -99,7 +99,7 @@ struct _MetaStack
    * The last-known stack of all windows, bottom to top.  We cache it here
    * so that subsequent times we'll be able to do incremental moves.
    */
-  GArray *last_root_children_stacked;
+  GArray *last_all_root_children_stacked;
 
   /**
    * Number of stack positions; same as the length of added, but
diff --git a/src/core/window-private.h b/src/core/window-private.h
index 044d89710..4827e58d5 100644
--- a/src/core/window-private.h
+++ b/src/core/window-private.h
@@ -80,10 +80,6 @@ typedef enum {
   _NET_WM_BYPASS_COMPOSITOR_HINT_OFF = 2,
 } MetaBypassCompositorHintValue;
 
-typedef enum {
-  META_WINDOW_CLIENT_TYPE_WAYLAND,
-  META_WINDOW_CLIENT_TYPE_X11
-} MetaWindowClientType;
 
 struct _MetaWindow
 {
diff --git a/src/core/window.c b/src/core/window.c
index df535289d..599965a51 100644
--- a/src/core/window.c
+++ b/src/core/window.c
@@ -1144,6 +1144,16 @@ meta_window_new_shared (MetaDisplay         *display,
   if (window->decorated)
     meta_window_ensure_frame (window);
 
+  if (window->client_type == META_WINDOW_CLIENT_TYPE_WAYLAND)
+    {
+      MetaStackWindow stack_window;
+      stack_window.any.type = META_WINDOW_CLIENT_TYPE_WAYLAND;
+      stack_window.wayland.meta_window = window;
+      meta_stack_tracker_record_add (window->screen->stack_tracker,
+                                     &stack_window,
+                                     0);
+    }
+
   meta_window_grab_keys (window);
   if (window->type != META_WINDOW_DOCK && !window->override_redirect)
     {
@@ -1832,6 +1842,16 @@ meta_window_unmanage (MetaWindow  *window,
 
   meta_verbose ("Unmanaging 0x%lx\n", window->xwindow);
 
+  if (window->client_type == META_WINDOW_CLIENT_TYPE_WAYLAND)
+    {
+      MetaStackWindow stack_window;
+      stack_window.any.type = META_WINDOW_CLIENT_TYPE_WAYLAND;
+      stack_window.wayland.meta_window = window;
+      meta_stack_tracker_record_remove (window->screen->stack_tracker,
+                                        &stack_window,
+                                        0);
+    }
+
   if (window->display->compositor)
     {
       if (window->visible_to_compositor)
diff --git a/src/meta/window.h b/src/meta/window.h
index 9679454ad..0b49c0343 100644
--- a/src/meta/window.h
+++ b/src/meta/window.h
@@ -81,6 +81,16 @@ typedef enum
   META_MAXIMIZE_VERTICAL   = 1 << 1
 } MetaMaximizeFlags;
 
+/**
+ * MetaWindowClientType:
+ * @META_WINDOW_CLIENT_TYPE_WAYLAND: A Wayland based window
+ * @META_WINDOW_CLIENT_TYPE_X11: An X11 based window
+ */
+typedef enum {
+  META_WINDOW_CLIENT_TYPE_WAYLAND,
+  META_WINDOW_CLIENT_TYPE_X11
+} MetaWindowClientType;
+
 #define META_TYPE_WINDOW            (meta_window_get_type ())
 #define META_WINDOW(obj)            (G_TYPE_CHECK_INSTANCE_CAST ((obj), META_TYPE_WINDOW, MetaWindow))
 #define META_WINDOW_CLASS(klass)    (G_TYPE_CHECK_CLASS_CAST ((klass),  META_TYPE_WINDOW, MetaWindowClass))