stacking order improvement

[mmc maruska dyndns org (Michal Maruška)]

hello,

last year (probably lost in the ML transition) i mentioned a problem of x-cycle
exposing some wrong windows uselessly.

The problem was, that at further steps (starting w/ the 2nd cycle), previous
stacking order is restored and and only then the new candidate (with possibly
its group, and transitient windows) is raised.  My proposal was to make all
those steps in 1 'transaction'.


I made progress in that area months ago, and would like to share the solution.
BUT: The C code doesn't contain a nice explanation of what is going on.
Even worse, the code is not polished. 
To understand it, it is necessary to read the explanation from
      http://citeseer.ist.psu.edu/myers86ond.html


The scheme api is the least complicated (for me):


*  the new SUBRs are:

- (set-restack-fast X)
     tells the other primitives (raise-window, ....) to just update the
     stacking-list C structure, but not issue the X calls. (if and only if X !=0)

Note: i realize, that 2 functions -enable and -disable could be more elegant,
      but i use this set-C-variable-directly approach for other features too.
      

- (commit-restacking old-list)
     pushes to the X server  the changes between OLD-LIST and current stacking order.

     
The big problem was to find a way to push the updated stacking order to the X
server. When pushing the entire list, X server was not clever enough, and with
many clients was too slow on such requests. So i decided to to use the O(nd)
algorithm (of Myers) to find the LCS (longest common subsequence), and optimize
at the client side.


* How to use it:   here is the only use for this new fieature(i know of):

x-cycle.jl
===========
..
    ;; start the transaction:
    (set-restack-fast 1)

    ;; take a snapshot of what we have now. (on the server)
    (let ((current-stacking-on-server (stacking-order)))
      
      (when (fluid x-cycle-stacking)
       ;; restore the original stacking:
        (restack-windows (fluid x-cycle-stacking)) ;  Go back
        (fluid-set x-cycle-stacking nil))
....
        (raise-window* win)
     ....


      ;; end the transaction
      (set-restack-fast 0)
      (commit-restacking (reverse current-stacking-on-server))
     )



* The patch to C:

** functions.c


int
set_int_variable(int* var, repv value)
{
   rep_DECLARE1 (value, rep_INTP);

   int old=*var;
   *var = rep_INT(value);
   return rep_MAKE_INT(old);
}


int restack_fast=0;   /* used by `restack_window' to do nothing.
                       * That is called from various x-lower/raise calls in this file: */

DEFUN("set-restack-fast", Fset_restack_fast, Sset_restack_fast, (repv debug), rep_Subr1) /*
::doc:sawfish.wm.events::set-restack-fast
make the following restacking operations immediate if 0, and posponed if 1
::end:: */
{
   rep_DECLARE1 (debug, rep_INTP);
   return set_int_variable(&restack_fast, debug);
}


#define MAX_X_WINDOWS    1000      /* fixme:   */
static Lisp_Window* backed_stacking[MAX_X_WINDOWS]; 


DEFUN("commit-restacking", Fcommit_restacking, Scommit_restacking, (repv list), rep_Subr1) /*(void), rep_Subr0) /*
::doc:sawfish.wm.events::set-restack-fast

called with the _old_ stacking order, which should be _still_ present in X.
Pushes the delayed stacking-order modifications to the X server.
::end:: */
{
   int i = 0;
   repv ptr;
   /* make the C array: */
   rep_DECLARE1(list, rep_LISTP);

   /* we want to operate on 2 vectors: move the list in a C array:  */

   if (list == Qnil)
      return Qt;                /* fixme: what if we have something now?
                                 * mmc: the 2 vectors have to contain the `same' set of windows. */

   for (ptr = list; rep_CONSP (ptr); ptr = rep_CDR (ptr))
      {
         if (!WINDOWP (rep_CAR (ptr)))
            return rep_signal_arg_error (list, 1);
         backed_stacking[i++] = (Lisp_Window*) rep_CAR (ptr);
      }

   push_stacking_list_to_server(backed_stacking, i);
   return Qt;
}




** stacking-list.c

extern int restack_fast;

void
restack_window (Lisp_Window *w)
{
+   if (restack_fast)
+      return;

   if (!WINDOW_IS_GONE_P (w))
...




*** And these new functions:

void
stack_window_below(Lisp_Window* w, Lisp_Window* the_one_above)
{
   XWindowChanges wc;
   wc.stack_mode = Below;
   wc.sibling = stackable_window_id (the_one_above);
   u_int mask = CWStackMode | CWSibling;
   XConfigureWindow (dpy, stackable_window_id (w), mask, &wc);
}




/* mmc's stacking:  using algorithm described here:
 * http://citeseer.ist.psu.edu/myers86ond.html
 */

#define MAX_X_WINDOWS    1000 /* fixme: */
   
static Lisp_Window* current_stacking[MAX_X_WINDOWS]; 
static int current_stacking_len;


   
static int
save_stacking_list_to_c_array(Lisp_Window** array)
{
   Lisp_Window *ptr;
   int i = 0;

   for (ptr = lowest_window; ptr != 0; ptr = ptr->above)
      array[i++] = ptr;
#if 0
   /* this is the `TOP' */
   array[i] = 0;
#endif
   return i;    /* i windows are present. */
}



/*  For the lcs problem, i consider 2 matrices:
 *    *  NxM  (N, M lenght of the sequences),
 *    *  the `level' matrix (d * max)
 *
 *    
 *    values in a row d in the level matrix are (a level of) x-coordinats, of ending points of edit paths of
 *    lenght d, ending at the diagonal k (of the NxM matrix).

 *   `max' is the upper bound of the number of necessary (possibly visited) diagonals. 
 *
 *      0      step    len        max
 *  0   ../.../.........|..........|
 *      ./.  /
 *level-/.../....X
 *      (level * 2 + 3)  ??
 *
 *
 *  */

inline
int
get(int* V, int max, int level, int step)
{
   return V[((level +1) * 2 + 1)* max + step];
}



inline
int
set(int* V, int max, int level, int step, int value)
{
   return V[(level * 2 + 3)* max + step] = value;
}

#define debug_stacking 0


typedef Lisp_Window* element;
#define EQUAL(x,y) (x==y)
/*  (x->id == y->id) */



/* M,N  lenghts,  a1, a2 the sequences being compared,  max,
 * return_k  ...
 * result_vector  ... the `matrix'(!) ...  (k,d) the x-coordinate of the longest k d-path */
int
lcs_myers_with_trace(int M, int N, element a1[], element a2[], int max,
                     int* return_k, int** results_vector)
{
   int d;
   int k;
   int x;
   int y;

   int* V = (int*) calloc((2 * max * (max + 1)), sizeof(element));
   /* bzero ?*/
   *results_vector = V;


   /* accessing it:  k(=>0) -> 2k
    *                k<0    -> 2k-1 */

   set(V, max, -1, 1, 0);        /* fixme:  s/0/-1/  then   */


   for (d = 0; d <= max; d++)   /* the level */
      {

         /* V (d,k)  the x coord. of the `longest' on the k, after d steps/differences.  we know, that it has form:
          * V(d-1,k+-1), followed by the longest snake */

         for (k= -d; k <= d ;k += 2)
            {
               if ((k == -d)    /* beginning of the level: we can only look upwards (not leftwards)*/
                   /* we _can_ look upwards, and indeed it's better:  */
                   || ( (k< d) && (get(V, max, d -1, k-1) < get(V, max, d-1, k+1)))) /* get returns the snake len?   x coordinate of the end?*/
                  x = get(V, max, d-1, k+1);      /* moving y coordinate  i.e upwards */
               else
                  x = get(V, max, d-1, k-1) + 1;  /* moving x   i.e. leftwards */

               y = x - k;

               /* snake */

               while ((x < M) && (y < N) && (EQUAL(a1[x],a2[y]))) /* stuff on the border ??? remains there ? */
                  ++x, ++y;

               /*  */
               set(V, max, d ,k, x);

               if ((x >= M) &&
                   (y >= N)){
                  *return_k = k;
                  return d;
               }
            };
      };
   return -1;                   /* nonsense ? */
}


/* we start with:
 *   
 *      myers_trace(table, max,  d, k, get(table, max, d, k), stacking, current_stacking, (element) NULL);
 *  
 *  Walk along the trace and issue the X calls.  This function is called recursively !!!
 *
 *  */


/* name of the window (above) */
#define  info_about(array, index)  ((array[index])?rep_STR( ((Lisp_Window*) array[index])->name):(u_char*)"top")

void
myers_trace(int V[], int max, int d, int k, int x, element s1[], element s2[], element last_fix)
{

   /* X is the x-coordinate: we know X from the previous iteration !!!
    *  
    * last_fix  is the element which is in the common subsequence.
    *
    *   |
    *   |
    *  _
    *   \_
    * */


   if (debug_stacking) DB(("\n** %s: max=%d d=%d k=%d x = %d\n", __FUNCTION__, max, d, k, x));

   if (d == 0)                  /* the whole prefix is equal in both sequences. nothing more to do */
      return;


/*
   Where to go: up or down?

   what if we go outside of used values ??  impossible

   if (d == k)
   (d == - k)
   -> only 1 direction!
*/

   int up   = (k==d)? -1: get(V, max, d-1 , k+1);
   int left = (-k==d)?-1: get(V, max, d-1, k-1);

   if (debug_stacking)
      DB(("comparing up: %d (%d %d) left: %d (%d %d)\n", up, d-1, k+1, left, d-1, k-1));
      
   /* fixme:  what is this?  */
   if (up > MAX_X_WINDOWS)
      if (debug_stacking)
         DB(("up was taken from max %d d %d k+1 %d, and is %d\n", max, d-1, k+1, up));

   if (left > MAX_X_WINDOWS)
      if (debug_stacking)
         DB(("left was taken from max %d d %d k-1 %d, and is %d\n", max, d-1, k-1, left));


   int y = left - (k-1);    /* fixme: we grow by 1 y  ??? */
   if (debug_stacking)
      DB(("x %d, up: %d, left %d(y: %d)\n", x, up, left, y));


   /* \ o
    *  x|
    *-o-x          x possible snake
    *    x|
    *
    *  */

   /* fixme: if one of this is out of the rectangle ???  */
      
   if ((up > left) || (y<0)){           /* if == take ??  But if lef == our position ?? */
      /* x is the same, and we have k+1 ?? */
         
      /*       x
       *      |
       *y      \
       *  */

      y = up - (k+1);

      if (x - up > 0)      /* we found some alligned elements: use the last one as the 'above' */
         {
            
            if (up < current_stacking_len) /* in 1st round this is false: so i ignore it for now: */
               {
                  last_fix = s1[up];
                  /* fixme: this is a non-issue: revert !!! */
                  if (debug_stacking)
                     DB(("new last_fix: %d %s\n", up, rep_STR(last_fix->name)));
               }
            
         };

      element this = s2[y];   

      if (!last_fix)         /* only at the top! */
         {
            XRaiseWindow(dpy, stackable_window_id((Lisp_Window*) this));
         }
      else
         {
            stack_window_below((Lisp_Window*) this, (Lisp_Window*) last_fix);
         }

      /* last_fix = this; */

      myers_trace(V, max, d-1, k+1, up, s1, s2, this);
   } else {
      if (debug_stacking)
         DB(("skipping backwards equal %d elements (snake), then delete %d (%s) from the server list. But we will move it elsewhere, so...\n",
             x - left -1, left, info_about(s1,left)));

      if (x - (left + 1) > 0)      /* we found some alligned elements: use the last one as the 'above' */
         {
            last_fix = s1[left + 1]; /* or + 2 ??? fixme! */
            DB(("setting last_fix to: %d %s\n", last_fix, rep_STR(last_fix->name)));
         };

      myers_trace(V, max, d-1, k-1, left, s1, s2, last_fix);
      /* these are x. We have  v == v  on which snake? */
   }
}


/*    sequence1  =  current server stacking order
 *              x->
 *   ---------------------------|
 *s2 | \
 * d |  \_____
 * e |        \
 * s |y        | add   X call!
 * i ||         \     
 * r |v          \____remove___  .. remove no X call!
 * e |                        |
 * d |                        |...
 *
 * */



/*
 *  `current_server_stacking'  is the stacking order on the X server. (len is the number of elements)
 *  Implicitly we use the data kept in this file ... lowest_window & 
 *
 *  This function finds what needs to be told to the X server, so that the stacking order (in X) is the same
 *  as the one kept here (in sawfish: lowest_window etc...)  The request is also sent to the X server.
 */
void
push_stacking_list_to_server(element current_server_stacking[], int len)  /* fixme: */
{
   int max, k, d;
   int *table;

   /* make a C _array_ from the sf-stacking-order data (in this file) */
   current_stacking_len = save_stacking_list_to_c_array(current_stacking);

   if (debug_stacking)
      DB(("%s: comparing 2 arrays with %d and %d elemens\n", __FUNCTION__, len, current_stacking_len));

   max = current_stacking_len + len; /* upper bound ? */


   /* find the difference */
   d = lcs_myers_with_trace(len, current_stacking_len, current_server_stacking, current_stacking,
                                  max, &k, &table);

   /* k should be 0. b/c both the stackings have the same # of elements. But we don't care. */
   if (debug_stacking)
      DB(("the difference is %d, the lenght of lcs is %d\n", d, current_stacking_len - (d / 2)));


   /* walk the difference, and emit the XRestackWindows */
   assert (get(table, max, d, k) == len); /* both lenghts should be equal, right?? */

   /* fixme: isn't d-k = m-n ? i.e. on the diagoal ?  err no. it should be k = m-n ? */
   myers_trace(table, max,  d, k, get(table, max, d, k), current_server_stacking, current_stacking, (element) NULL);
   free(table);
}




the entire files (my up-to-date version) can be seen at:

http://maruska.dyndns.org/comp/activity/sawfish/src/stacking-list.c
http://maruska.dyndns.org/comp/activity/sawfish/src/functions.c



PS: i am trying to extract other reasonable patches from my sources, which are
    full of "tracing instructions" and personal notes.  Not that this first
    patch is not. But i hope this code is easy to clean, and is quite short.

    The features provided by them are:
    1/  reliable/deterministic processing of window-closing wrt refocusing

    2/ reliable handling of focus & grabs. I.e handling all grabs with the
    precision of single key events, and ungrabbing only after the refocusing.
    

    i wrote a _little_ about it here:
          http://maruska.dyndns.org/wiki/sawfish-getting-right.html

    and all the C sources are at http://maruska.dyndns.org/comp/activity/sawfish/src/