Subject: bug#73533: closed (Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants)

From: [email-masked] (GNU bug Tracking System)
Date: Sat, 19 Oct 2024 17:43:02 +0000

Your bug report

#73533: [PATCH] Rewrite speedbar expansion for all descendants

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
73533: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=73533
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
From: Eli Zaretskii <[email-masked]>
To: Morgan Willcock <[email-masked]>
Cc: [email-masked]
Date: Sat, 19 Oct 2024 20:41:37 +0300
List-Id: <debbugs-submit.debbugs.gnu.org>

> From: Morgan Willcock <[email-masked]>
> Cc: [email-masked]
> Date: Sat, 19 Oct 2024 18:30:13 +0100
> 
> Eli Zaretskii <[email-masked]> writes:
> 
> > There seems to be still a problem with some files, in that
> > speedbar-expand-line-descendants takes a very long time, and if I
> > interrupt it with C-g, I see nested DEFUNs, something that shouldn't
> > happen, because DEFUNs are never nested.  E.g., try this:
> >
> >  $ cd /path/to/emacs/src
> >  $ ./emacs -Q
> >  M-x speedbar RET
> >
> > At this point you should see all the files in the Emacs src directory.
> > Go to androidfns.c and type '['.  After about 10 sec type C-g.  You
> > should see nested DEFUns in the Speedbar frame.
> >
> > Could you please look into this?
> 
> This looks like an unrelated issue where the logic to modify the item
> hierarchy does not make sense under certain conditions.  It only seems
> to trigger when particular limits are met, but the limits can be lowered
> for an easier demonstration:
> 
>   (require 'speedbar)
>   (setq speedbar-tag-regroup-maximum-length 2)
>   (setq speedbar-tag-split-minimum-length 2)
> 
>   (speedbar-prefix-group-tag-hierarchy
>    '(("DEFUN" . 1)
>      ("DEFUN" . 5)
>      ("DEFUN" . 10)))
> 
>   => (("DEFUN" ("DEFUN" . 1) ("DEFUN" . 5) ("DEFUN" . 10)))
> 
> i.e. speedbar-prefix-group-tag-hierarchy (which is meant to restructure
> the Imenu data to make better use of the available space in the
> Speedbar) is generating a new parent item which contains the items that
> were meant to be inserted.
> 
> It is probably best to open a separate bug report for this because
> working out exactly how and why speedbar-prefix-group-tag-hierarchy
> applies particular sorting actions will probably take someone a while.

Done, and closing.

Thanks.

Subject: [PATCH] Rewrite speedbar expansion for all descendants
From: Morgan Willcock <[email-masked]>
To: [email-masked]
Date: Sat, 28 Sep 2024 20:05:26 +0100
List-Id: <debbugs-submit.debbugs.gnu.org>

Tags: patch

Attached is a patch which rewrites 'speedbar-expand-line-descendants'.

The previous version could get into an infinite loop by reaching the
maximum recursion depth, although in practice the slow speed meant that
most people would probably abort the operation before reaching that
point.

The majority of the slowdown was because the motion commands being used
were the variants which looked up information for every entry, displayed
the information as a message, and adjusted the cursor position.  The
messages were not readable because of being continually overwritten.

Here is a way to demonstrate that stack depth was increasing for items
at the same level, that the messages were not readable, and how slow the
whole process was:

  rm -rf /tmp/project
  mkdir /tmp/project
  for i in $(seq 1 50); do echo "(defun fun-$i ())" >> /tmp/project/file1.el; done
  for i in $(seq 1 50); do echo "(defun fun-$i ())" >> /tmp/project/file2.el; done
  emacs -Q \
        --eval="(find-file \"/tmp/project/file1.el\")" \
        --eval "(speedbar-get-focus)" \
        --eval "(profiler-start 'cpu)" \
        --eval "(speedbar-expand-line-descendants)" \
        --eval "(profiler-stop)" \
        --eval "(profiler-report)"

...that should expand every entry in file1.el and not touch the entries
in file2.el.

The replacement function is significantly faster.  Messages are only
used to indicate that the function is running and when it is finished -
the result is similar to manually clicking every node open.

Thanks,
Morgan

In GNU Emacs 30.0.91 (build 2, x86_64-pc-linux-gnu, X toolkit, cairo
 version 1.16.0, Xaw3d scroll bars) of 2024-09-12 built on inspiron
Windowing system distributor 'The X.Org Foundation', version 11.0.12101007
System Description: Debian GNU/Linux 12 (bookworm)

Configured using:
 'configure --with-native-compilation=aot --with-xml2
 --with-x-toolkit=lucid'

>From 0e25d28bfbef31c20ec22c2e508933b3824a8172 Mon Sep 17 00:00:00 2001
From: Morgan Willcock <[email-masked]>
Date: Sat, 28 Sep 2024 19:11:11 +0100
Subject: [PATCH] Rewrite speedbar expansion for all descendants

Rewrite 'speedbar-expand-line-descendants' to avoid getting into
an infinite loop by reaching max-lisp-eval-depth.  The new
method avoids querying and displaying information for every
movement, instead using a single message to indicate that
expansion is in progress, and so is significantly faster.

* lisp/speedbar.el (speedbar-expand-line-descendants): Use
simpler line motion and no recursion.  Output messages
indicating when expansion is in progress and when it is
completed.
---
 lisp/speedbar.el | 31 ++++++++++++++++---------------
 1 file changed, 16 insertions(+), 15 deletions(-)

diff --git a/lisp/speedbar.el b/lisp/speedbar.el
index c13c977938b..11e11e1e56c 100644
--- a/lisp/speedbar.el
+++ b/lisp/speedbar.el
@@ -3172,21 +3172,22 @@ speedbar-expand-line-descendants
   "Expand the line under the cursor and all descendants.
 Optional argument ARG indicates that any cache should be flushed."
   (interactive "P")
-  (save-restriction
-    (narrow-to-region (line-beginning-position)
-                      (line-beginning-position 2))
-    (speedbar-expand-line arg)
-    ;; Now, inside the area expanded here, expand all subnodes of
-    ;; the same descendant type.
-    (save-excursion
-      (speedbar-next 1) ;; Move into the list.
-      (let ((err nil))
-        (while (not err)
-	  (condition-case nil
-	      (progn
-	        (speedbar-expand-line-descendants arg)
-	        (speedbar-restricted-next 1))
-	    (error (setq err t))))))))
+  (dframe-message "Expanding all descendants...")
+  (save-excursion
+    (with-restriction
+        ;; Narrow around the top-level item.
+        (line-beginning-position)
+        (condition-case nil
+            (save-excursion
+              (speedbar-restricted-move 1)
+              (line-beginning-position))
+          (error (line-beginning-position 2)))
+      ;; Expand every line until the end of the restriction.
+      (while (zerop (progn
+                      (speedbar-expand-line arg)
+                      (forward-line 1))))))
+  (dframe-message "Expanding all descendants...done")
+  (speedbar-position-cursor-on-line))
 
 (defun speedbar-contract-line-descendants ()
   "Expand the line under the cursor and all descendants."
-- 
2.39.5