Re: gnus crashes on threads deeper than 333 articles

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

Chris Moore <christopher.ian.moore@gmail.com> writes:

> I just tried opening a mail folder using nnimap in gnus.
>
> One of the threads in the folder is 834 messages long, and each
> message in the thread is a reply to the previous one which results in
> the thread being 834 messages 'deep'.
>
> The definition of gnus-sort-threads in lisp/gnus/gnus-sum.el does
> this:
>     (let ((max-lisp-eval-depth 5000))
> but it doesn't increase max-specpdl-size.  Maybe it should?
>
> Or maybe it shouldn't impose fixed limits on the maximum allowable
> thread length at all.  A re-implementation using a loop instead of
> recursion should be able to get around this limit.  It's walking the
> thread tree, sorting as it goes.

The attached patch provides a reimplementation of gnus-sort-threads-1
that uses a loop instead of recursion.  It may be a little too
intricate a change to check into Emacs at this point, though.  What do
people think?

*** emacs/lisp/gnus/gnus-sum.el.~1.93.~	2006-11-24 14:49:06.000000000 -0500
--- emacs/lisp/gnus/gnus-sum.el	2006-12-03 15:25:31.000000000 -0500
***************
*** 4550,4560 ****
  	    (gnus-delete-line)))))))
  
  (defun gnus-sort-threads-1 (threads func)
!   (sort (mapcar (lambda (thread)
! 		  (cons (car thread)
! 			(and (cdr thread)
! 			     (gnus-sort-threads-1 (cdr thread) func))))
! 		threads) func))
  
  (defun gnus-sort-threads (threads)
    "Sort THREADS."
--- 4550,4569 ----
  	    (gnus-delete-line)))))))
  
  (defun gnus-sort-threads-1 (threads func)
!   (let* ((superthread (cons nil threads))
! 	 (stack (list (cons superthread threads)))
! 	 remaining-threads thread)
!     (while stack
!       (setq remaining-threads (cdr (car stack)))
!       (if remaining-threads
! 	  (progn (setq thread (car remaining-threads))
! 		 (setcdr (car stack) (cdr remaining-threads))
! 		 (if (cdr thread)
! 		     (push (cons thread (cdr thread)) stack)))
! 	(setq thread (caar stack))
! 	(setcdr thread (sort (cdr thread) func))
! 	(pop stack)))
!     (cdr superthread)))
  
  (defun gnus-sort-threads (threads)
    "Sort THREADS."

Re: gnus crashes on threads deeper than 333 articles

[Richard Stallman]

That change is needed, and not too big.
If it works, please install it.

Re: gnus crashes on threads deeper than 333 articles

[Reiner Steib]

On Sun, Dec 03 2006, Chong Yidong wrote:

> Chris Moore <christopher.ian.moore@gmail.com> writes:
>
>> I just tried opening a mail folder using nnimap in gnus.
>>
>> One of the threads in the folder is 834 messages long, and each
>> message in the thread is a reply to the previous one which results in
>> the thread being 834 messages 'deep'.
>>
>> The definition of gnus-sort-threads in lisp/gnus/gnus-sum.el does
>> this:
>>     (let ((max-lisp-eval-depth 5000))
>> but it doesn't increase max-specpdl-size.  Maybe it should?
>>
>> Or maybe it shouldn't impose fixed limits on the maximum allowable
>> thread length at all.  A re-implementation using a loop instead of
>> recursion should be able to get around this limit.  It's walking the
>> thread tree, sorting as it goes.
>
> The attached patch provides a reimplementation of gnus-sort-threads-1
> that uses a loop instead of recursion.  It may be a little too
> intricate a change to check into Emacs at this point, though.  What do
> people think?

I searched the archives and I only found one more report about this
problem, so it seems to be a *very rare* situation.  I'm not sure if
such a change should be made now (in the stable series).

What about providing an option and keep the current recursive as
default?  See the patch below (`gnus-sort-threads-loop' is your
function).

Is your implementation faster or slower than the recursion?

--8<---------------cut here---------------start------------->8---
--- gnus-sum.el	09 Nov 2006 13:32:35 +0100	7.163
+++ gnus-sum.el	04 Dec 2006 16:55:43 +0100	
@@ -4649,20 +4649,48 @@
 	      (1+ (point-at-eol))
 	    (gnus-delete-line)))))))
 
-(defun gnus-sort-threads-1 (threads func)
+(defun gnus-sort-threads-recursive (threads func)
   (sort (mapcar (lambda (thread)
 		  (cons (car thread)
 			(and (cdr thread)
-			     (gnus-sort-threads-1 (cdr thread) func))))
+			     (gnus-sort-threads-recursive (cdr thread) func))))
 		threads) func))
 
+(defun gnus-sort-threads-loop (threads func)
+  (let* ((superthread (cons nil threads))
+	 (stack (list (cons superthread threads)))
+	 remaining-threads thread)
+    (while stack
+      (setq remaining-threads (cdr (car stack)))
+      (if remaining-threads
+	  (progn (setq thread (car remaining-threads))
+		 (setcdr (car stack) (cdr remaining-threads))
+		 (if (cdr thread)
+		     (push (cons thread (cdr thread)) stack)))
+	(setq thread (caar stack))
+	(setcdr thread (sort (cdr thread) func))
+	(pop stack)))
+    (cdr superthread)))
+
+(defcustom gnus-sort-threads-function 'gnus-sort-threads-recursive
+  "Function used to sort threads.
+There are two pre-defined functions:
+`gnus-sort-threads-recursive', and `gnus-sort-threads-loop'.  If
+you get an error message \"Variable binding depth exceeds
+max-specpdl-size\" during threading, set this variable to
+`gnus-sort-threads-loop'."
+  :group 'gnus-thread
+  :version "22.1" ;; Gnus 5.10.9
+  :type '(choice (const :tag "recursion" gnus-sort-threads-recursive)
+		 (const :tag "loop" gnus-sort-threads-loop)))
+
 (defun gnus-sort-threads (threads)
   "Sort THREADS."
   (if (not gnus-thread-sort-functions)
       threads
     (gnus-message 8 "Sorting threads...")
     (let ((max-lisp-eval-depth 5000))
-      (prog1 (gnus-sort-threads-1
+      (prog1 (funcall gnus-sort-threads-function
 	 threads
 	 (gnus-make-sort-function gnus-thread-sort-functions))
         (gnus-message 8 "Sorting threads...done")))))
--8<---------------cut here---------------end--------------->8---

Bye, Reiner.
-- 
       ,,,
      (o o)
---ooO-(_)-Ooo---  |  PGP key available  |  http://rsteib.home.pages.de/

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Richard Stallman <rms@gnu.org> writes:

> That change is needed, and not too big.
> If it works, please install it.

I don't think it does work quite right.

I've tried opening the mailbox with the long thread and it still
doesn't work.  I get a different error now though:

  Debugger entered--Lisp error: (args-out-of-range ["" "    " "        " "            " "                " "                    " " 
    aref(["" "    " "        " "            " "                " "                    " "                        " "                
    (setq gnus-tmp-indentation (aref gnus-thread-indent-array gnus-tmp-level) gnus-tmp-lines (mail-header-lines gnus-tmp-header) gnu
    (progn (when (and gnus-tmp-dummy-line ...) (gnus-summary-insert-dummy-line gnus-tmp-dummy-line ...) (setq gnus-tmp-dummy-line ni
    (if gnus-tmp-header (progn (when ... ... ...) (setq gnus-tmp-unread ...) (push ... gnus-newsgroup-data) (setq gnus-tmp-subject-o
    (when gnus-tmp-header (when (and gnus-tmp-dummy-line ...) (gnus-summary-insert-dummy-line gnus-tmp-dummy-line ...) (setq gnus-tm
    (if (stringp gnus-tmp-header) (cond (... ... ... ... ...) (... ... ...) (... ... ...) (t ...)) (setq number (mail-header-number 
    (while (or threads stack gnus-tmp-new-adopts new-roots) (if (and ... ... ... ...) (if gnus-tmp-new-adopts ... ...) (if threads .
    (if (vectorp (car threads)) (gnus-summary-prepare-unthreaded threads) (if gnus-summary-display-while-building (switch-to-buffer 
    (let ((gnus-tmp-level 0) (default-score ...) (gnus-visual-p ...) (building-line-count gnus-summary-display-while-building) (buil
    gnus-summary-prepare-threads((("[CaravelNet (Forum Games)] Re: Guess the Screenshot!" ([53 "[CaravelNet (Forum Games)] Re: Guess
    (progn (gnus-summary-prepare-threads (if gnus-show-threads ... ...)))
    (if gnus-newsgroup-headers (progn (gnus-summary-prepare-threads ...)))
    (when gnus-newsgroup-headers (gnus-summary-prepare-threads (if gnus-show-threads ... ...)))
    (let ((buffer-read-only nil)) (erase-buffer) (setq gnus-newsgroup-data nil gnus-newsgroup-data-reverse nil) (gnus-run-hooks (quo
    gnus-summary-prepare()
    (if no-display nil (gnus-summary-prepare))
    (unless no-display (gnus-summary-prepare))
    (cond ((not new-group) (gnus-set-global-variables) (when kill-buffer ...) (gnus-configure-windows ... ...) (gnus-set-mode-line .
    (let* ((new-group ...) (quit-config ...) (did-select ...)) (cond (... ... ... ... ... ... ... t) (... ... ... nil) (... ... ... 
    gnus-summary-read-group-1("fun.drod" t nil nil nil nil)
    (or (gnus-summary-read-group-1 group show-all no-article kill-buffer no-display select-articles) (setq show-all nil select-artic
    (let ((gnus-auto-select-next nil)) (or (gnus-summary-read-group-1 group show-all no-article kill-buffer no-display select-articl
    (setq result (let (...) (or ... ...)))
    (null (setq result (let ... ...)))
    (and group (null (setq result ...)) (eq gnus-auto-select-next (quote quietly)))
    (while (and group (null ...) (eq gnus-auto-select-next ...)) (set-buffer gnus-group-buffer) (when backward (gnus-group-prev-unre
    (let (result) (while (and group ... ...) (set-buffer gnus-group-buffer) (when backward ...) (if ... ... ...)) result)
    gnus-summary-read-group("fun.drod" t nil nil nil nil nil)
    gnus-group-read-group(nil nil "fun.drod")
    gnus-fetch-group("fun.drod")
    call-interactively(gnus-fetch-group)

One thing I noticed it that the new sort funcction changes the length
of the list of threads:

  *** Welcome to IELM ***  Type (describe-mode) for help.
  ELISP> (length before-sorting)
  106
  ELISP> (length after-sorting)
  258
  ELISP> before-sorting
  *** IELM Error ***  Error during pretty-printing (bug in pp)
  ELISP> (print before-sorting)
  *** Eval error ***  Apparently circular structure being printed
  ELISP> (prin1 before-sorting)
  *** Eval error ***  Apparently circular structure being printed
  ELISP> print-circle
  nil
  ELISP> (setq print-circle t)
  t
  ELISP> before-sorting
  *** IELM Error ***  Error during pretty-printing (bug in pp)
  ELISP> (print before-sorting)
  *** Eval error ***  Apparently circular structure being printed
  ELISP> 

but I'm not able to work out how to view the list, due to "bug in pp"
and "apparently circular structure" errors.

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Chris Moore <christopher.ian.moore@gmail.com> writes:

> One thing I noticed it that the new sort funcction changes the length
> of the list of threads:
>
>   *** Welcome to IELM ***  Type (describe-mode) for help.
>   ELISP> (length before-sorting)
>   106
>   ELISP> (length after-sorting)
>   258

That seems to be a red herring.  Running the new sort function on
before-sorting gives a list the same length as running the old sort
function does.  I tried using 'equal to compare the 2 outputs, but got
a stack overflow error.

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Chris Moore <christopher.ian.moore@gmail.com> writes:

> Chris Moore <christopher.ian.moore@gmail.com> writes:
>
>> One thing I noticed it that the new sort funcction changes the length
>> of the list of threads:
>>
>>   *** Welcome to IELM ***  Type (describe-mode) for help.
>>   ELISP> (length before-sorting)
>>   106
>>   ELISP> (length after-sorting)
>>   258
>
> That seems to be a red herring.  Running the new sort function on
> before-sorting gives a list the same length as running the old sort
> function does.  I tried using 'equal to compare the 2 outputs, but got
> a stack overflow error.

OK, so the 'loop' version of the sort function does seem to work, but
fixing that has shown up a new problem.

The '200' and '201' in this function limit the thread depth.
Increasing these numbers has allowed me to finally open my large
Increasing these mailbox!

  (defun gnus-make-thread-indent-array ()
    (let ((n 200))
      (unless (and gnus-thread-indent-array
  		 (= gnus-thread-indent-level gnus-thread-indent-array-level))
        (setq gnus-thread-indent-array (make-vector 201 "")

Re: gnus crashes on threads deeper than 333 articles

[Reiner Steib]

On Mon, Dec 04 2006, Chris Moore wrote:

> OK, so the 'loop' version of the sort function does seem to work, but
> fixing that has shown up a new problem.
>
[ gnus-make-thread-indent-array ]
> The '200' and '201' in this function limit the thread depth.

I'd suggest the following patch on top of the previous.  Which size
was sufficient for you?

--8<---------------cut here---------------start------------->8---
--- gnus-sum.el	08 Nov 2006 00:45:38 +0100	7.163
+++ gnus-sum.el	04 Dec 2006 19:54:43 +0100	
@@ -3442,11 +3442,14 @@
       t
     (not (cdr (gnus-data-find-list article)))))
 
+(defvar gnus-make-thread-indent-array-size 400)
+
 (defun gnus-make-thread-indent-array ()
-  (let ((n 200))
+  (let ((n gnus-make-thread-indent-array-size))
     (unless (and gnus-thread-indent-array
 		 (= gnus-thread-indent-level gnus-thread-indent-array-level))
-      (setq gnus-thread-indent-array (make-vector 201 "")
+      (setq gnus-thread-indent-array
+	    (make-vector (1+ gnus-make-thread-indent-array-size) "")
 	    gnus-thread-indent-array-level gnus-thread-indent-level)
       (while (>= n 0)
 	(aset gnus-thread-indent-array n
--8<---------------cut here---------------end--------------->8---

> Increasing these numbers has allowed me to finally open my large
> Increasing these mailbox!

Another workaround would be to turn off threading for this group,
wouldn't it?  I mean, from your description threading seems quite
useless for this group.

Bye, Reiner.
-- 
       ,,,
      (o o)
---ooO-(_)-Ooo---  |  PGP key available  |  http://rsteib.home.pages.de/

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

Reiner Steib <reinersteib+gmane@imap.cc> writes:

> I searched the archives and I only found one more report about this
> problem, so it seems to be a *very rare* situation.  I'm not sure if
> such a change should be made now (in the stable series).
>
> What about providing an option and keep the current recursive as
> default?  See the patch below (`gnus-sort-threads-loop' is your
> function).

I think this is a good approach.

> Is your implementation faster or slower than the recursion?

After testing it on several comp.* newsgroups, I concluded that the
performance difference is statistically insignificant.

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Reiner Steib <reinersteib+gmane@imap.cc> writes:

> I'd suggest the following patch on top of the previous.  Which size
> was sufficient for you?

I used 2000 instead of 200.  Can the array be made to grow as needed,
rather than having a hard limit to the maximum thread depth?

> Another workaround would be to turn off threading for this group,
> wouldn't it?  I mean, from your description threading seems quite
> useless for this group.

You're right, that would work around the problem, but I'd rather see
it fixed for everyone than just worked-around for me.

Re: gnus crashes on threads deeper than 333 articles

[Richard Stallman]

    > What about providing an option and keep the current recursive as
    > default?  See the patch below (`gnus-sort-threads-loop' is your
    > function).

    I think this is a good approach.

Why do we want to keep the recursive version?
Why add an option?

We know that the loop works, so let's just use that.

Re: gnus crashes on threads deeper than 333 articles

[Reiner Steib]

On Tue, Dec 05 2006, Richard Stallman wrote:

>     > What about providing an option and keep the current recursive as
>     > default?  See the patch below (`gnus-sort-threads-loop' is your
>     > function).
>
>     I think this is a good approach.
>
> Why do we want to keep the recursive version?
> Why add an option?
>
> We know that the loop works, so let's just use that.

Well, the recursion is well tested (part of Gnus at least since 1997)
with only _two_ reported problems with it over all those years
(i.e. the situation when the recursion fails is *very rare*).  The new
function has been tested in practice only by two persons.  I wouldn't
feel comfortable to change such an important function so shortly
before the Emacs release without providing a simple way back in case
of problem with the loop implementation.

Bye, Reiner.
-- 
       ,,,
      (o o)
---ooO-(_)-Ooo---  |  PGP key available  |  http://rsteib.home.pages.de/

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

How about this patch?  Instead of adding a new defcustom, we use the
safe recursive sorter by default, and try again with the non-recursive
sorter if an error is signalled.  The patch also regenerates
gnus-thread-indent-array if it becomes too small to handle a thread.

*** emacs/lisp/gnus/gnus-sum.el.~1.93.~	2006-11-24 14:49:06.000000000 -0500
--- emacs/lisp/gnus/gnus-sum.el	2006-12-05 11:50:25.000000000 -0500
***************
*** 3343,3358 ****
        t
      (not (cdr (gnus-data-find-list article)))))
  
! (defun gnus-make-thread-indent-array ()
!   (let ((n 200))
!     (unless (and gnus-thread-indent-array
! 		 (= gnus-thread-indent-level gnus-thread-indent-array-level))
!       (setq gnus-thread-indent-array (make-vector 201 "")
! 	    gnus-thread-indent-array-level gnus-thread-indent-level)
!       (while (>= n 0)
! 	(aset gnus-thread-indent-array n
! 	      (make-string (* n gnus-thread-indent-level) ? ))
! 	(setq n (1- n))))))
  
  (defun gnus-update-summary-mark-positions ()
    "Compute where the summary marks are to go."
--- 3343,3358 ----
        t
      (not (cdr (gnus-data-find-list article)))))
  
! (defun gnus-make-thread-indent-array (&optional n)
!   (if (null n) (setq n 200))
!   (unless (and gnus-thread-indent-array
! 	       (= gnus-thread-indent-level gnus-thread-indent-array-level))
!     (setq gnus-thread-indent-array (make-vector 201 "")
! 	  gnus-thread-indent-array-level gnus-thread-indent-level)
!     (while (>= n 0)
!       (aset gnus-thread-indent-array n
! 	    (make-string (* n gnus-thread-indent-level) ? ))
!       (setq n (1- n)))))
  
  (defun gnus-update-summary-mark-positions ()
    "Compute where the summary marks are to go."
***************
*** 3451,3456 ****
--- 3451,3459 ----
  				 gnus-tmp-expirable gnus-tmp-subject-or-nil
  				 &optional gnus-tmp-dummy gnus-tmp-score
  				 gnus-tmp-process)
+   (if (> gnus-tmp-level (length gnus-thread-indent-array))
+       (gnus-make-thread-indent-array (max (* 2 (length gnus-thread-indent-array))
+ 					  gnus-tmp-level)))
    (let* ((gnus-tmp-indentation (aref gnus-thread-indent-array gnus-tmp-level))
  	 (gnus-tmp-lines (mail-header-lines gnus-tmp-header))
  	 (gnus-tmp-score (or gnus-tmp-score gnus-summary-default-score 0))
***************
*** 4549,4571 ****
  	      (1+ (gnus-point-at-eol))
  	    (gnus-delete-line)))))))
  
! (defun gnus-sort-threads-1 (threads func)
    (sort (mapcar (lambda (thread)
  		  (cons (car thread)
  			(and (cdr thread)
  			     (gnus-sort-threads-1 (cdr thread) func))))
  		threads) func))
  
  (defun gnus-sort-threads (threads)
    "Sort THREADS."
    (if (not gnus-thread-sort-functions)
        threads
      (gnus-message 8 "Sorting threads...")
!     (let ((max-lisp-eval-depth 5000))
!       (prog1 (gnus-sort-threads-1
! 	 threads
! 	 (gnus-make-sort-function gnus-thread-sort-functions))
!         (gnus-message 8 "Sorting threads...done")))))
  
  (defun gnus-sort-articles (articles)
    "Sort ARTICLES."
--- 4552,4597 ----
  	      (1+ (gnus-point-at-eol))
  	    (gnus-delete-line)))))))
  
! (defun gnus-sort-threads-recursive (threads func)
    (sort (mapcar (lambda (thread)
  		  (cons (car thread)
  			(and (cdr thread)
  			     (gnus-sort-threads-1 (cdr thread) func))))
  		threads) func))
  
+ (defun gnus-sort-threads-loop (threads func)
+   (let* ((superthread (cons nil threads))
+   	 (stack (list (cons superthread threads)))
+   	 remaining-threads thread)
+     (while stack
+       (setq remaining-threads (cdr (car stack)))
+       (if remaining-threads
+   	  (progn (setq thread (car remaining-threads))
+   		 (setcdr (car stack) (cdr remaining-threads))
+   		 (if (cdr thread)
+   		     (push (cons thread (cdr thread)) stack)))
+   	(setq thread (caar stack))
+   	(setcdr thread (sort (cdr thread) func))
+   	(pop stack)))
+     (cdr superthread)))
+ 
  (defun gnus-sort-threads (threads)
    "Sort THREADS."
    (if (not gnus-thread-sort-functions)
        threads
      (gnus-message 8 "Sorting threads...")
!     (prog1
! 	(condition-case nil
! 	    (let ((max-lisp-eval-depth (max max-lisp-eval-depth 5000)))
! 	      (gnus-sort-threads-recursive
! 	       threads (gnus-make-sort-function gnus-thread-sort-functions)))
! 	  ;; Even after binding max-lisp-eval-depth, the recursive
! 	  ;; sorter might fail for very long threads.  In that case,
! 	  ;; fall back on a (less well-tested) non-recursive sorter.
! 	  (error (gnus-sort-threads-loop
! 		  threads (gnus-make-sort-function
! 			   gnus-thread-sort-functions))))
!       (gnus-message 8 "Sorting threads...done")))))
  
  (defun gnus-sort-articles (articles)
    "Sort ARTICLES."
***************
*** 4990,4995 ****
--- 5016,5025 ----
  		      gnus-tmp-closing-bracket ?\>)
  	      (setq gnus-tmp-opening-bracket ?\[
  		    gnus-tmp-closing-bracket ?\]))
+ 	    (if (> gnus-tmp-level (length gnus-thread-indent-array))
+ 		(gnus-make-thread-indent-array
+ 		 (max (* 2 (length gnus-thread-indent-array))
+ 		      gnus-tmp-level)))
  	    (setq
  	     gnus-tmp-indentation
  	     (aref gnus-thread-indent-array gnus-tmp-level)
***************
*** 8165,8171 ****
    ;; will really go down to a leaf article first, before slowly
    ;; working its way up towards the root.
    (when thread
!     (let* ((max-lisp-eval-depth 5000)
  	   (children
  	   (if (cdr thread)
  	       (apply '+ (mapcar 'gnus-summary-limit-children
--- 8195,8201 ----
    ;; will really go down to a leaf article first, before slowly
    ;; working its way up towards the root.
    (when thread
!     (let* ((max-lisp-eval-depth (max 5000 max-lisp-eval-depth))
  	   (children
  	   (if (cdr thread)
  	       (apply '+ (mapcar 'gnus-summary-limit-children

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

> How about this patch?  Instead of adding a new defcustom, we use the
> safe recursive sorter by default, and try again with the non-recursive
> sorter if an error is signalled.  The patch also regenerates
> gnus-thread-indent-array if it becomes too small to handle a thread.

Oops, a couple typos in that patch.  I meant this:

*** gnus-sum.el.~1.93.~	2006-11-24 14:49:06.000000000 -0500
--- gnus-sum.el	2006-12-05 11:58:31.000000000 -0500
***************
*** 3343,3358 ****
        t
      (not (cdr (gnus-data-find-list article)))))
  
! (defun gnus-make-thread-indent-array ()
!   (let ((n 200))
!     (unless (and gnus-thread-indent-array
! 		 (= gnus-thread-indent-level gnus-thread-indent-array-level))
!       (setq gnus-thread-indent-array (make-vector 201 "")
! 	    gnus-thread-indent-array-level gnus-thread-indent-level)
!       (while (>= n 0)
! 	(aset gnus-thread-indent-array n
! 	      (make-string (* n gnus-thread-indent-level) ? ))
! 	(setq n (1- n))))))
  
  (defun gnus-update-summary-mark-positions ()
    "Compute where the summary marks are to go."
--- 3343,3358 ----
        t
      (not (cdr (gnus-data-find-list article)))))
  
! (defun gnus-make-thread-indent-array (&optional n)
!   (if (null n) (setq n 200))
!   (unless (and gnus-thread-indent-array
! 	       (= gnus-thread-indent-level gnus-thread-indent-array-level))
!     (setq gnus-thread-indent-array (make-vector 201 "")
! 	  gnus-thread-indent-array-level gnus-thread-indent-level)
!     (while (>= n 0)
!       (aset gnus-thread-indent-array n
! 	    (make-string (* n gnus-thread-indent-level) ? ))
!       (setq n (1- n)))))
  
  (defun gnus-update-summary-mark-positions ()
    "Compute where the summary marks are to go."
***************
*** 3451,3456 ****
--- 3451,3459 ----
  				 gnus-tmp-expirable gnus-tmp-subject-or-nil
  				 &optional gnus-tmp-dummy gnus-tmp-score
  				 gnus-tmp-process)
+   (if (> gnus-tmp-level (length gnus-thread-indent-array))
+       (gnus-make-thread-indent-array (max (* 2 (length gnus-thread-indent-array))
+ 					  gnus-tmp-level)))
    (let* ((gnus-tmp-indentation (aref gnus-thread-indent-array gnus-tmp-level))
  	 (gnus-tmp-lines (mail-header-lines gnus-tmp-header))
  	 (gnus-tmp-score (or gnus-tmp-score gnus-summary-default-score 0))
***************
*** 4549,4571 ****
  	      (1+ (gnus-point-at-eol))
  	    (gnus-delete-line)))))))
  
! (defun gnus-sort-threads-1 (threads func)
    (sort (mapcar (lambda (thread)
  		  (cons (car thread)
  			(and (cdr thread)
! 			     (gnus-sort-threads-1 (cdr thread) func))))
  		threads) func))
  
  (defun gnus-sort-threads (threads)
    "Sort THREADS."
    (if (not gnus-thread-sort-functions)
        threads
      (gnus-message 8 "Sorting threads...")
!     (let ((max-lisp-eval-depth 5000))
!       (prog1 (gnus-sort-threads-1
! 	 threads
! 	 (gnus-make-sort-function gnus-thread-sort-functions))
!         (gnus-message 8 "Sorting threads...done")))))
  
  (defun gnus-sort-articles (articles)
    "Sort ARTICLES."
--- 4552,4597 ----
  	      (1+ (gnus-point-at-eol))
  	    (gnus-delete-line)))))))
  
! (defun gnus-sort-threads-recursive (threads func)
    (sort (mapcar (lambda (thread)
  		  (cons (car thread)
  			(and (cdr thread)
! 			     (gnus-sort-threads-recursive (cdr thread) func))))
  		threads) func))
  
+ (defun gnus-sort-threads-loop (threads func)
+   (let* ((superthread (cons nil threads))
+   	 (stack (list (cons superthread threads)))
+   	 remaining-threads thread)
+     (while stack
+       (setq remaining-threads (cdr (car stack)))
+       (if remaining-threads
+   	  (progn (setq thread (car remaining-threads))
+   		 (setcdr (car stack) (cdr remaining-threads))
+   		 (if (cdr thread)
+   		     (push (cons thread (cdr thread)) stack)))
+   	(setq thread (caar stack))
+   	(setcdr thread (sort (cdr thread) func))
+   	(pop stack)))
+     (cdr superthread)))
+ 
  (defun gnus-sort-threads (threads)
    "Sort THREADS."
    (if (not gnus-thread-sort-functions)
        threads
      (gnus-message 8 "Sorting threads...")
!     (prog1
! 	(condition-case nil
! 	    (let ((max-lisp-eval-depth (max max-lisp-eval-depth 5000)))
! 	      (gnus-sort-threads-recursive
! 	       threads (gnus-make-sort-function gnus-thread-sort-functions)))
! 	  ;; Even after binding max-lisp-eval-depth, the recursive
! 	  ;; sorter might fail for very long threads.  In that case,
! 	  ;; fall back on a (less well-tested) non-recursive sorter.
! 	  (error (gnus-sort-threads-loop
! 		  threads (gnus-make-sort-function
! 			   gnus-thread-sort-functions))))
!       (gnus-message 8 "Sorting threads...done"))))
  
  (defun gnus-sort-articles (articles)
    "Sort ARTICLES."
***************
*** 4990,4995 ****
--- 5016,5025 ----
  		      gnus-tmp-closing-bracket ?\>)
  	      (setq gnus-tmp-opening-bracket ?\[
  		    gnus-tmp-closing-bracket ?\]))
+ 	    (if (> gnus-tmp-level (length gnus-thread-indent-array))
+ 		(gnus-make-thread-indent-array
+ 		 (max (* 2 (length gnus-thread-indent-array))
+ 		      gnus-tmp-level)))
  	    (setq
  	     gnus-tmp-indentation
  	     (aref gnus-thread-indent-array gnus-tmp-level)
***************
*** 8165,8171 ****
    ;; will really go down to a leaf article first, before slowly
    ;; working its way up towards the root.
    (when thread
!     (let* ((max-lisp-eval-depth 5000)
  	   (children
  	   (if (cdr thread)
  	       (apply '+ (mapcar 'gnus-summary-limit-children
--- 8195,8201 ----
    ;; will really go down to a leaf article first, before slowly
    ;; working its way up towards the root.
    (when thread
!     (let* ((max-lisp-eval-depth (max 5000 max-lisp-eval-depth))
  	   (children
  	   (if (cdr thread)
  	       (apply '+ (mapcar 'gnus-summary-limit-children

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Chong Yidong <cyd@stupidchicken.com> writes:

> How about this patch?  Instead of adding a new defcustom, we use the
> safe recursive sorter by default, and try again with the non-recursive
> sorter if an error is signalled.  The patch also regenerates
> gnus-thread-indent-array if it becomes too small to handle a thread.

> ! (defun gnus-make-thread-indent-array (&optional n)
> !   (if (null n) (setq n 200))
> !   (unless (and gnus-thread-indent-array
> ! 	       (= gnus-thread-indent-level gnus-thread-indent-array-level))
> !     (setq gnus-thread-indent-array (make-vector 201 "")

That 201 should be (1+ n)?

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

Chris Moore <dooglus@gmail.com> writes:

> Chong Yidong <cyd@stupidchicken.com> writes:
>
>> How about this patch?  Instead of adding a new defcustom, we use the
>> safe recursive sorter by default, and try again with the non-recursive
>> sorter if an error is signalled.  The patch also regenerates
>> gnus-thread-indent-array if it becomes too small to handle a thread.
>
>> ! (defun gnus-make-thread-indent-array (&optional n)
>> !   (if (null n) (setq n 200))
>> !   (unless (and gnus-thread-indent-array
>> ! 	       (= gnus-thread-indent-level gnus-thread-indent-array-level))
>> !     (setq gnus-thread-indent-array (make-vector 201 "")
>
> That 201 should be (1+ n)?

Yep.

Re: gnus crashes on threads deeper than 333 articles

[Chris Moore]

Chong Yidong <cyd@stupidchicken.com> writes:

>> How about this patch?  Instead of adding a new defcustom, we use the
>> safe recursive sorter by default, and try again with the non-recursive
>> sorter if an error is signalled.  The patch also regenerates
>> gnus-thread-indent-array if it becomes too small to handle a thread.
>
> Oops, a couple typos in that patch.  I meant this:

That's the same as you said before...

Re: gnus crashes on threads deeper than 333 articles

[Richard Stallman]

      I wouldn't
    feel comfortable to change such an important function so shortly
    before the Emacs release without providing a simple way back in case
    of problem with the loop implementation.

This is a simple, localized bug fix, and I'd rather fix the bug than
have it in the release.  That's what pretesting is for--to fix bugs.

Re: gnus crashes on threads deeper than 333 articles

[Chong Yidong]

> Instead of adding a new defcustom, we use the safe recursive sorter
> by default, and try again with the non-recursive sorter if an error
> is signalled.  The patch also regenerates gnus-thread-indent-array
> if it becomes too small to handle a thread.

Any objections to this approach?