C-g while exiting the minibuffer

C-g while exiting the minibuffer

[Stefan Monnier]

I've been trying to track down a performance problem I've been
experimenting for a while now.  Along the way I found that the problem
shows up when frame-focus is redirected (at least, it's a necessary
ingredient, tho not sufficient).

But I also found out that sometimes I have a redirected frame-focus for
no reason.  And I finally yesterday caught the bugger that causes this:
C-h right while exiting the minibuffer: my minibuffer is in a separate
frame, so while in the minibuffer, the frame-focus is redirected (this
is perfectly normal so far).  When exiting the minibuffer, this focus is
supposed to be canceled, but this cancellation can fail:

the cancellation is done implicitly by the restoration of the previous
window-configuration.  The problem being that Fset_window_configuration
does

      /* In the following call to `select-window', prevent "swapping out
	 point" in the old selected window using the buffer that has
	 been restored into it.  We already swapped out that point from
	 that window's old buffer.  */
      select_window (data->current_window, Qnil, 1);
      BVAR (XBUFFER (XWINDOW (selected_window)->contents), last_selected_window)
	= selected_window;

just before

      if (NILP (data->focus_frame)
	  || (FRAMEP (data->focus_frame)
	      && FRAME_LIVE_P (XFRAME (data->focus_frame))))
	Fredirect_frame_focus (frame, data->focus_frame);

IOW just before resetting the frame-focus, we select the
selected-window.  So far this looks innocuous, but select_window (with
a 1 as last argument) calls record_buffer which calls Fdelq which uses
QUIT, so if you happen to hit C-g at the right time, the frame-focus
redirection is not properly canceled.

Now I wonder what should be the best way to fix this.  I can just switch
the above two code blocks, which will fix the immediate problem (a C-g
will not prevent canceling the frame-focus redirected), but I think this
points to a larger problem of hitting C-g while processing unwind forms.
Of course binding inhibit-quit during processing of unwind forms could
be a source of problem in itself (if those forms fail to terminate).

Any comment/idea/suggestion?


        Stefan

Re: C-g while exiting the minibuffer

[Stefan Monnier]

> Any comment/idea/suggestion?

A further question: in Fset_window_configuration, a bit after calling
select_window (which may QUIT on us), we call adjust_frame_glyphs and we
also free glyph matrices in windows that were not reused.

Is it OK not to do those steps if we QUIT?


        Stefan

Re: C-g while exiting the minibuffer

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Wed, 27 Nov 2013 20:54:15 -0500
> 
> > Any comment/idea/suggestion?
> 
> A further question: in Fset_window_configuration, a bit after calling
> select_window (which may QUIT on us), we call adjust_frame_glyphs and we
> also free glyph matrices in windows that were not reused.
> 
> Is it OK not to do those steps if we QUIT?

Only if we are sure the window configuration didn't change a bit.

IOW, it is safer to always do that, just in case.

Re: C-g while exiting the minibuffer

[Stefan Monnier]

>> > Any comment/idea/suggestion?
>> A further question: in Fset_window_configuration, a bit after calling
>> select_window (which may QUIT on us), we call adjust_frame_glyphs and we
>> also free glyph matrices in windows that were not reused.
>> Is it OK not to do those steps if we QUIT?
> Only if we are sure the window configuration didn't change a bit.

IOW it is *not* safe.  So we have a bug right there.


        Stefan

Re: C-g while exiting the minibuffer

[martin rudalics]

[-- Attachment #1: Type: text/plain, Size: 968 bytes --]

 > Now I wonder what should be the best way to fix this.  I can just switch
 > the above two code blocks, which will fix the immediate problem (a C-g
 > will not prevent canceling the frame-focus redirected), but I think this
 > points to a larger problem of hitting C-g while processing unwind forms.
 > Of course binding inhibit-quit during processing of unwind forms could
 > be a source of problem in itself (if those forms fail to terminate).

I still have hare/tortoise implementations of Fset_window_prev_buffers
and Fset_window_next_buffers (for pure curiosity I attach the
corresponding part of a larger patch here).  Chong didn't want to
install them then because he considered it overengineering.  Installing
them means select_window could safely modify these lists with quitting
inhibited.

Calling `buffer-list-update-hook' would have to be deferred until the
end of `set-window-configuration' - no great deal IMHO.

Do you see any more problems?

martin

[-- Attachment #2: prev-next-buffers.diff --]
[-- Type: text/plain, Size: 2701 bytes --]

=== modified file 'src/window.c'
--- src/window.c	2012-02-23 17:40:33 +0000
+++ src/window.c	2012-02-27 07:43:06 +0000
@@ -51,7 +51,7 @@
 #endif
 
 Lisp_Object Qwindowp, Qwindow_live_p;
-static Lisp_Object Qwindow_configuration_p, Qrecord_window_buffer;
+static Lisp_Object Qwindow_configuration_p;
 static Lisp_Object Qwindow_deletable_p, Qdelete_window, Qdisplay_buffer;
 static Lisp_Object Qreplace_buffer_in_windows, Qget_mru_window;
 static Lisp_Object Qwindow_resize_root_window, Qwindow_resize_root_window_vertically;
@@ -1647,15 +1647,41 @@
 
 DEFUN ("set-window-prev-buffers", Fset_window_prev_buffers,
        Sset_window_prev_buffers, 2, 2, 0,
-       doc: /* Set WINDOW's previous buffers to PREV-BUFFERS.
+       doc:	     /* Set WINDOW's previous buffers to PREV-BUFFERS.
 WINDOW must be a live window and defaults to the selected one.
 
 PREV-BUFFERS should be a list of elements (BUFFER WINDOW-START POS),
 where BUFFER is a buffer, WINDOW-START is the start position of the
 window for that buffer, and POS is a window-specific point value.  */)
-     (Lisp_Object window, Lisp_Object prev_buffers)
+  (Lisp_Object window, Lisp_Object prev_buffers)
 {
-  return decode_window (window)->prev_buffers = prev_buffers;
+  register struct window *w = decode_window (window);
+
+  if (NILP (prev_buffers))
+    return w->prev_buffers = Qnil;
+  else if (!CONSP (prev_buffers))
+    return w->prev_buffers;
+  else
+    {
+      /* Run cycle detection on prev_buffers.  */
+      Lisp_Object tortoise, hare;
+
+      hare = tortoise = prev_buffers;
+      while (CONSP (hare))
+	{
+	  hare = XCDR (hare);
+	  if (!CONSP (hare))
+	    break;
+
+	  hare = XCDR (hare);
+	  tortoise = XCDR (tortoise);
+
+	  if (EQ (hare, tortoise))
+	    return w->prev_buffers;
+	}
+
+      return w->prev_buffers = prev_buffers;
+    }
 }
 
 DEFUN ("window-next-buffers", Fwindow_next_buffers, Swindow_next_buffers,
@@ -1674,7 +1700,33 @@
 NEXT-BUFFERS should be a list of buffers.  */)
      (Lisp_Object window, Lisp_Object next_buffers)
 {
-  return decode_window (window)->next_buffers = next_buffers;
+  register struct window *w = decode_window (window);
+
+  if (NILP (next_buffers))
+    return w->next_buffers = Qnil;
+  else if (!CONSP (next_buffers))
+    return w->next_buffers;
+  else
+    {
+      /* Run cycle detection on next_buffers.  */
+      Lisp_Object tortoise, hare;
+
+      hare = tortoise = next_buffers;
+      while (CONSP (hare))
+	{
+	  hare = XCDR (hare);
+	  if (!CONSP (hare))
+	    break;
+
+	  hare = XCDR (hare);
+	  tortoise = XCDR (tortoise);
+
+	  if (EQ (hare, tortoise))
+	    return w->next_buffers;
+	}
+
+      return w->next_buffers = next_buffers;
+    }
 }
 

Re: C-g while exiting the minibuffer

[Stefan Monnier]

> I still have hare/tortoise implementations of Fset_window_prev_buffers
> and Fset_window_next_buffers (for pure curiosity I attach the
> corresponding part of a larger patch here).  Chong didn't want to
> install them then because he considered it overengineering.  Installing
> them means select_window could safely modify these lists with quitting
> inhibited.

To tell you the truth, I'm not worried about the risk of non-termination
if we inhibit quit during record_buffer (even with the current code).
I do agree that if we did that, we might want to use a hare/tortoise
thingy to avoid inf-loops, but the main problem for me is whether we
want to inhibit quit or not and if we do, over which part of the code.

Generally we prefer not to inhibit quit, and instead we order statements
in such a way that any intermediate point is safe.  I'll probably
install a patch following this principle.

But the problem remains of what to do with a C-g interrupting a unwind
form: in the case of an Fset_window_configuration in an unwind form, the
intention is to make that "no matter what happens, we end up recovering
the original state", but a C-g at the wrong time will break this promise.

>  {
> -  return decode_window (window)->prev_buffers = prev_buffers;
> +  register struct window *w = decode_window (window);
> +
> +  if (NILP (prev_buffers))
> +    return w->prev_buffers = Qnil;
> +  else if (!CONSP (prev_buffers))
> +    return w->prev_buffers;
> +  else
> +    {
> +      /* Run cycle detection on prev_buffers.  */
> +      Lisp_Object tortoise, hare;
> +
> +      hare = tortoise = prev_buffers;
> +      while (CONSP (hare))
> +	{
> +	  hare = XCDR (hare);
> +	  if (!CONSP (hare))
> +	    break;
> +
> +	  hare = XCDR (hare);
> +	  tortoise = XCDR (tortoise);
> +
> +	  if (EQ (hare, tortoise))
> +	    return w->prev_buffers;
> +	}
> +
> +      return w->prev_buffers = prev_buffers;
> +    }
>  }

comments:
- we used to have a "DOLIST" kind of macro which did the hare/tortoise
  thing in lisp.h.  Not sure what happened to it, but I'd rather use
  such a macro then duplicate the corresponding code wherever we have
  such a loop.
- checking cycles here gives us no guarantee since the caller can do

    (set-window-prev-buffers w bufs)
    (setcdr bufs bufs)

  and you again end up with a cycle in your window-prev-buffers.


-- Stefan

Re: C-g while exiting the minibuffer

[Andreas Schwab]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> - we used to have a "DOLIST" kind of macro which did the hare/tortoise
>   thing in lisp.h.  Not sure what happened to it,

It didn't last long.

2001-10-14  Stefan Monnier  <monnier@cs.yale.edu>

        * xdisp.c (DOLIST, LOOP_PROPVAL): Remove.

2001-10-12  Stefan Monnier  <monnier@cs.yale.edu>

        * xdisp.c
        (DOLIST, LOOP_PROPVAL): New macros.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: C-g while exiting the minibuffer

[Stefan Monnier]

>> - we used to have a "DOLIST" kind of macro which did the hare/tortoise
>> thing in lisp.h.  Not sure what happened to it,
> It didn't last long.
> 2001-10-14  Stefan Monnier  <monnier@cs.yale.edu>
>         * xdisp.c (DOLIST, LOOP_PROPVAL): Remove.
> 2001-10-12  Stefan Monnier  <monnier@cs.yale.edu>
>         * xdisp.c (DOLIST, LOOP_PROPVAL): New macros.

Hmmm... I think I was remembering another one.  Was this DOLIST using
hare/tortoise?  IIRC the hare/tortoise macro was written by Gerd and was
in src/lisp.h.


        Stefan

Re: C-g while exiting the minibuffer

[Stefan Monnier]

Found it:

    revno: 39564
    committer: Gerd Moellmann <gerd@gnu.org>
    timestamp: Fri 2001-10-05 09:48:47 +0000
    message:
      (LIST_END_P, FOREACH): New macros.


   /* Loop over Lisp list LIST.  Signal an error if LIST is not a proper
      list, or if it contains circles.
      
      HARE and TORTOISE should be the names of Lisp_Object variables, and
      N should be the name of an EMACS_INT variable declared in the
      function where the macro is used.  Each nested loop should use
      its own variables.
   
      In the loop body, HARE is set to each cons of LIST, and N is the
      length of the list processed so far.  */
   
   #define LIST_END_P(list, obj)				\
     (NILP (obj)						\
      ? 1							\
      : (CONSP (obj)					\
         ? 0						\
         : (wrong_type_argument (Qlistp, (list), 0)), 1))
   
   #define FOREACH(hare, list, tortoise, n)		\
     for (tortoise = hare = (list), n = 0;			\
          !LIST_END_P (list, hare);			\
          (hare = XCDR (hare), ++n,			\
   	((n & 1) != 0					\
   	 ? (tortoise = XCDR (tortoise),			\
   	    (EQ (hare, tortoise)			\
   	     && (circular_list_error ((list)), 1)))	\
   	 : 0)))

Died in 2011:

    revno: 103880.1.17
    committer: Paul Eggert <eggert@cs.ucla.edu>
    branch nick: atest
    timestamp: Mon 2011-04-11 22:17:33 -0700
    message:
      * lisp.h (circular_list_error, FOREACH): Remove; unused.


-- Stefan

Re: C-g while exiting the minibuffer

[martin rudalics]

 > But the problem remains of what to do with a C-g interrupting a unwind
 > form: in the case of an Fset_window_configuration in an unwind form, the
 > intention is to make that "no matter what happens, we end up recovering
 > the original state", but a C-g at the wrong time will break this promise.

I'm afraid that C-g at the wrong time might produce an inconsistent
state which IMO seems more fatal than a non-original state.

 > - we used to have a "DOLIST" kind of macro which did the hare/tortoise
 >   thing in lisp.h.  Not sure what happened to it, but I'd rather use
 >   such a macro then duplicate the corresponding code wherever we have
 >   such a loop.

Agreed.

 > - checking cycles here gives us no guarantee since the caller can do
 >
 >     (set-window-prev-buffers w bufs)
 >     (setcdr bufs bufs)
 >
 >   and you again end up with a cycle in your window-prev-buffers.

Right.  So we'd need a safe implementation of delq and I wouldn't know
how to do that reasonably via DOLIST.  I'd rather use a simple routine
to find out whether the original argument list of delq is infinite (if
we think this could be a real problem).

martin

Re: C-g while exiting the minibuffer

[Stefan Monnier]

>> But the problem remains of what to do with a C-g interrupting a unwind
>> form: in the case of an Fset_window_configuration in an unwind form, the
>> intention is to make that "no matter what happens, we end up recovering
>> the original state", but a C-g at the wrong time will break this promise.
> I'm afraid that C-g at the wrong time might produce an inconsistent
> state which IMO seems more fatal than a non-original state.

An inconsistent state would also be a non-original state, so yes, an
inconsistent would also break the promise.

>> - checking cycles here gives us no guarantee since the caller can do
>> (set-window-prev-buffers w bufs)
>> (setcdr bufs bufs)
>> and you again end up with a cycle in your window-prev-buffers.
> Right.  So we'd need a safe implementation of delq and I wouldn't know
> how to do that reasonably via DOLIST.

Indeed, the FOREACH macro was designed for "read-only" traversals, just
like the DOLIST macro.  I don't think the hare/tortoise trick is
inapplicable, tho: it just requires more care (since the deletions of
Fdelq might give the tortoise shortcuts that risk making the tortoise
catch up with the hare).  See patch below.

> I'd rather use a simple routine to find out whether the original
> argument list of delq is infinite (if we think this could be a real
> problem).

I think the hare/tortoise is a "simple routine to find out if the list is
infinite".


        Stefan


=== modified file 'src/fns.c'
--- src/fns.c	2013-11-29 19:47:58 +0000
+++ src/fns.c	2013-12-01 22:02:46 +0000
@@ -1537,15 +1537,12 @@
 the value of a list `foo'.  */)
   (register Lisp_Object elt, Lisp_Object list)
 {
-  register Lisp_Object tail, prev;
-  register Lisp_Object tem;
+  Lisp_Object tail, tortoise, prev = Qnil;
+  bool skip;
 
-  tail = list;
-  prev = Qnil;
-  while (CONSP (tail))
+  FOR_EACH_TAIL (tail, list, tortoise, skip)
     {
-      CHECK_LIST_CONS (tail, list);
-      tem = XCAR (tail);
+      Lisp_Object tem = XCAR (tail);
       if (EQ (elt, tem))
 	{
 	  if (NILP (prev))
@@ -1555,8 +1552,6 @@
 	}
       else
 	prev = tail;
-      tail = XCDR (tail);
-      QUIT;
     }
   return list;
 }

=== modified file 'src/lisp.h'
--- src/lisp.h	2013-11-30 09:25:31 +0000
+++ src/lisp.h	2013-12-01 22:05:02 +0000
@@ -4443,6 +4443,20 @@
       memory_full (SIZE_MAX);				       \
   } while (0)
 
+/* Loop over all tails of a list, checking for cycles.
+   FIXME: Make tortoise and n internal declarations.
+   FIXME: Unroll the loop body so we don't need `n'.  */
+#define FOR_EACH_TAIL(hare, list, tortoise, n)	\
+  for (tortoise = hare = (list), n = true;			\
+       CONSP (hare);						\
+       (hare = XCDR (hare), n = !n,				\
+   	(n							\
+   	 ? ((EQ (hare, tortoise)				\
+	     && (xsignal1 (Qcircular_list, (list)), 0)))	\
+	 /* Move tortoise before the next iteration, in case */ \
+	 /* the next iteration does an Fsetcdr.  */		\
+   	 : (tortoise = XCDR (tortoise), 0))))
+
 /* Do a `for' loop over alist values.  */
 
 #define FOR_EACH_ALIST_VALUE(head_var, list_var, value_var)		\

Re: C-g while exiting the minibuffer

[Stephen J. Turnbull]

Stefan Monnier writes:

 > > Right.  So we'd need a safe implementation of delq and I wouldn't know
 > > how to do that reasonably via DOLIST.
 > 
 > Indeed, the FOREACH macro was designed for "read-only" traversals, just
 > like the DOLIST macro.  I don't think the hare/tortoise trick is
 > inapplicable, tho:

AFAIK XEmacs has done it that way for a decade.  To my inexpert eye,
your patch looks very much like the code we use.  For more info, call
Martin Buchholz (mrb@xemacs.org).

Re: C-g while exiting the minibuffer

[martin rudalics]

 > Indeed, the FOREACH macro was designed for "read-only" traversals, just
 > like the DOLIST macro.  I don't think the hare/tortoise trick is
 > inapplicable, tho: it just requires more care (since the deletions of
 > Fdelq might give the tortoise shortcuts that risk making the tortoise
 > catch up with the hare).  See patch below.

I wanted to study its logic but I see that you installed it already.
IIRC there are a few more places where I wanted something similar -
these will have to wait.

Thanks, martin