Index: ChangeLog
===================================================================
RCS file: /cvs/gnome/metacity/ChangeLog,v
retrieving revision 1.797
diff -p -u -r1.797 ChangeLog
--- ChangeLog	15 Feb 2004 14:42:15 -0000	1.797
+++ ChangeLog	16 Feb 2004 00:37:30 -0000
@@ -1,3 +1,23 @@
+2004-02-15  Rob Adams  <readams@readams.net>
+
+	Handle layer promotion of transient descendants of layer-promoted
+	windows to also be layer promoted, using a simple iterative
+	algorithm.
+
+	* src/stack.c (compute_layer): change name to promote_layer, and
+	convert to simply perform any necessary layer promotion without
+	computing the standalone layer.
+	(max_layer_func): use window->layer instead of
+	get_standalone_layer
+	(get_maximum_layer_of_ancestor): use window->layer instead of
+	get_standalone_layer
+	(meta_stack_ensure_sorted): implement iterative algorithm,
+	explained in a long comment.
+	
+	* src/window.h: add a tmp_layer field used by stack.c for
+	determining if the stack is dirty or not, since maintaining this
+	information in meta_stack_ensure_sorted is no longer practical.
+	
 2004-02-15  Anders Carlsson  <andersca@gnome.org>
 
 	* src/menu.c (meta_window_menu_new): Actually translate a message,
Index: src/stack.c
===================================================================
RCS file: /cvs/gnome/metacity/src/stack.c,v
retrieving revision 1.67
diff -p -u -r1.67 stack.c
--- src/stack.c	19 Aug 2003 20:10:45 -0000	1.67
+++ src/stack.c	16 Feb 2004 00:38:00 -0000
@@ -290,11 +290,9 @@ max_layer_func (MetaWindow *window,
                 void       *data)
 {
   MaxLayerData *d = data;
-  MetaStackLayer layer;
   
-  layer = get_standalone_layer (window);
-  if (layer > d->max)
-    d->max = layer;
+  if (window->layer > d->max)
+    d->max = window->layer;
 
   return TRUE;
 }
@@ -304,7 +302,7 @@ get_maximum_layer_of_ancestor (MetaWindo
 {
   MaxLayerData d;
 
-  d.max = get_standalone_layer (window);
+  d.max = window->layer;
   meta_window_foreach_ancestor (window, max_layer_func, &d);
   
   return d.max;
@@ -349,10 +347,8 @@ get_maximum_layer_in_group (MetaWindow *
 }
 
 static void
-compute_layer (MetaWindow *window)
+promote_layer (MetaWindow *window)
 {
-  window->layer = get_standalone_layer (window);
-  
   /* We can only do promotion-due-to-group for dialogs and other
    * transients, or weird stuff happens like the desktop window and
    * nautilus windows getting in the same layer, or all gnome-terminal
@@ -387,16 +383,6 @@ compute_layer (MetaWindow *window)
            * and a dialog transient for the normal window; you don't want the dialog
            * above the dock if it wouldn't normally be.
            */
-
-          /* FIXME when promoting a window here,
-           * it's necessary to promote its transient children
-           * (or other windows constrained to be above it)
-           * as well, but we aren't handling that, and it's
-           * somewhat hard to fix.
-           *
-           * http://bugzilla.gnome.org/show_bug.cgi?id=96140
-           */
-          
           MetaStackLayer group_max;
           
           group_max = get_maximum_layer_in_group (window);
@@ -913,34 +899,99 @@ meta_stack_ensure_sorted (MetaStack *sta
   /* Update the layers that windows are in */
   if (stack->need_relayer)
     {
+      gint layers_dirty;
+
       meta_topic (META_DEBUG_STACK,
                   "Recomputing layers\n");
-      
+
       tmp = stack->sorted;
+      while (tmp != NULL)
+	{
+	  MetaWindow *w;
+	  w = tmp->data;
+
+	  w->tmp_layer = w->layer;
+	  w->layer = get_standalone_layer(w);
+
+	  tmp = tmp->next;
+	}
+
+      /* Keep track of group or transient-induced layer promotion;
+       * iterate until we reach a fixed point.
+       *
+       * Note that we know this will terminate because in each
+       * iteration at least one window is promoted, and each window
+       * can only be promoted a fixed number of times.  So we can
+       * iterate at most only O(n) times where n is the number of
+       * windows.  More precisely, though, it will iterate at most
+       * once for each window in the longest chain of transient
+       * dependents, which in general won't be more than 2-3 windows
+       * long.
+       *
+       * Overall though, since promote_layer is potentially O(n)
+       * itself, this is worst-case O(n^3) in the case where every
+       * window is in a chain of transients starting at a dock window
+       * and the windows are in reverse order in the stack order to
+       * begin with.  In practice, this will never happen, and for
+       * real users the complexity behaves like O(n), since for real
+       * desktops the number of levels of transience is
+       * constant-bounded.  This could be done in overall worst-case
+       * O(n lg n) time by constructing a constraint graph and
+       * serializing it in the same way that the stacking works for
+       * windows within a layer, but I suspect this would often be
+       * slower than this algorithm.
+       *
+       * We don't need to constrain as constraining purely operates in
+       * terms of stack_position not layer
+       */
+      layers_dirty = TRUE;
+
+      while (layers_dirty)
+        {
+          layers_dirty = FALSE;
+          tmp = stack->sorted;
+
+          while (tmp != NULL)
+            {
+              MetaWindow *w;
+              MetaStackLayer old_layer;
+              
+              w = tmp->data;
+              old_layer = w->layer;
+              
+              promote_layer (w);
+              
+              if (w->layer != old_layer)
+                {
+                  /* if we promoted a window in this iteration, and
+                   * that window has a transient descendant, we'll
+                   * have to do another iteration.  Unfortunately,
+                   * finding out if a window has transient descendants
+                   * is just as expensive as simply doing another
+                   * iteration, so we'll just always do the iteration.
+                   */
+                  layers_dirty = TRUE;
+                }
+              
+              tmp = tmp->next;
+            }
+        }
 
+      tmp = stack->sorted;
       while (tmp != NULL)
         {
           MetaWindow *w;
-          MetaStackLayer old_layer;
-
           w = tmp->data;
-          old_layer = w->layer;
 
-          compute_layer (w);
-
-          if (w->layer != old_layer)
+          if (w->tmp_layer != w->layer)
             {
               meta_topic (META_DEBUG_STACK,
                           "Window %s moved from layer %d to %d\n",
-                          w->desc, old_layer, w->layer);
-              
+                          w->desc, w->tmp_layer, w->layer);
+                     
               stack->need_resort = TRUE;
-              /* don't need to constrain as constraining
-               * purely operates in terms of stack_position
-               * not layer
-               */
             }
-          
+
           tmp = tmp->next;
         }
 
Index: src/window.h
===================================================================
RCS file: /cvs/gnome/metacity/src/window.h,v
retrieving revision 1.99
diff -p -u -r1.99 window.h
--- src/window.h	13 Dec 2003 23:00:06 -0000	1.99
+++ src/window.h	16 Feb 2004 00:38:24 -0000
@@ -286,6 +286,7 @@ struct _MetaWindow
 
   /* Managed by stack.c */
   MetaStackLayer layer;
+  MetaStackLayer tmp_layer;
   int stack_position; /* see comment in stack.h */
   
   /* Current dialog open for this window */
