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

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

[Morgan Willcock]

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

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'


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Rewrite-speedbar-expansion-for-all-descendants.patch --]
[-- Type: text/patch, Size: 2447 bytes --]

From 0e25d28bfbef31c20ec22c2e508933b3824a8172 Mon Sep 17 00:00:00 2001
From: Morgan Willcock <morgan@ice9.digital>
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

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

[Eli Zaretskii]

> From: Morgan Willcock <morgan@ice9.digital>
> Date: Sat, 28 Sep 2024 20:05:26 +0100
> 
> 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.  Unfortunately, speedbar doesn't have a test suite, so I would
like to ask how you tested this rewrite, and whether we could have
some tests for this added to the test suite.

Regardless, it would be good to have both old and the new code
annotated with explanations of what each non-trivial line does, to
allow independent verification of the correctness of the rewrite by
people who are not familiar with speedbar code and don't immediately
understand the effects of a call to speedbar-naxt or
speedbar-restricted-move.

Also, this comment in the old code bothers me:

> -    ;; Now, inside the area expanded here, expand all subnodes of
> -    ;; the same descendant type.

What does it mean by "the same descendant type", and how does the old
and the new code make sure they expand only those descendants?

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

[Morgan Willcock]

Eli Zaretskii <eliz@gnu.org> writes:

> Thanks.  Unfortunately, speedbar doesn't have a test suite, so I would
> like to ask how you tested this rewrite, and whether we could have
> some tests for this added to the test suite.

I've been testing by expanding all descendent items interactively,
either with test files which generate a lot of items or within the Emacs
source tree.

I wouldn't be against adding tests but it doesn't look like there are
many ways to query the speedbar state, which is probably why the
original code is not testing whether nodes are expandable before trying
to expand them.  Both the original and the new code and fundamentally
doing the same thing by assuming that each new line may be expanded and
trying to expand it - moving "into" a sub-list is just moving forward
because if expansion was possible it has occurred.

I could probably craft a test which would demonstrate the old code
hitting a recursion limit, but fundamentally the problem was the speed
and excessive message output.

> Regardless, it would be good to have both old and the new code
> annotated with explanations of what each non-trivial line does, to
> allow independent verification of the correctness of the rewrite by
> people who are not familiar with speedbar code and don't immediately
> understand the effects of a call to speedbar-naxt or
> speedbar-restricted-move.

speedbar-next = forward-line + display message for item + reposition
cursor

speedbar-restricted-move = move to the next item in the list at the
current level or signal an error if the end of the list is reached

speedbar-restricted-next = speedbar-restricted-move + display message
for item

Here is the original code my comments instead of the original comments:

  (defun speedbar-expand-line-descendants (&optional arg)
    "Expand the line under the cursor and all descendants.
  Optional argument ARG indicates that any cache should be flushed."
    (interactive "P")
    (save-restriction
      ;; The recursion of the original code means that sibling items below
      ;; the first item were also being accidentally expanded.  Narrow the
      ;; buffer around the current item to prevent opening all sibling
      ;; items.  bug#35014
      (narrow-to-region (line-beginning-position)
                        (line-beginning-position 2))
      ;; Assume that the current line can be expanded.
      (speedbar-expand-line arg)
      (save-excursion
        ;; Move forward.  Where current line did not expand this
        ;; effectively moves to the next sibling or the end of the buffer
        ;; restriction.  Display a description of the newly moved to item
        ;; as a message.  Readjust the column position of point.
        (speedbar-next 1)
        ;; Loop across all siblings until an error is signalled.
        (let ((err nil))
          (while (not err)
            (condition-case nil
                (progn
                  ;; Assume that the item is expandable and recursively
                  ;; expand it.
                  (speedbar-expand-line-descendants arg)
                  ;; Move to the next item at the current level or signal
                  ;; an error.  Display a description of the newly moved
                  ;; to item as a message.
                  (speedbar-restricted-next 1))
              (error (setq err t))))))))

To stop the continual stream of messages and cursor repositioning of
calling speedbar-next, it can just be replaced with forward-line because
that is all speedbar-next does to move.

To stop the continual stream of messages from speedbar-restricted-next
it can just be replaced with speedbar-restricted-move which is exactly
the same thing but without the message output.

So the majority of the speedup is just done by those two replacements,
and all that should have changed is that now no messages are being
produced.  To make it non-recursive and add the status message to
indicate that something is happening, what I've actually done is change
the fix which was applied for bug#35014.  Instead of narrowing
recursively to avoid accidentally running into siblings, the narrowing
is setup once by using speedbar-restricted-move to find the next
sibling.  The logic for expansion is effectively still the same as a
depth first traversal but without the messages being generated:

  (defun speedbar-expand-line-descendants (&optional arg)
    "Expand the line under the cursor and all descendants.
  Optional argument ARG indicates that any cache should be flushed."
    (interactive "P")
    (dframe-message "Expanding all descendants...")
    (save-excursion
      (with-restriction
          ;; Narrow around the top-level item to ensure that later sibling
          ;; items will not be entered.
          (line-beginning-position)
          (condition-case nil
              (save-excursion
                (speedbar-restricted-move 1)
                ;; The line beginning position of the next sibling item.
                (line-beginning-position))
            ;; This was the last sibling item so just apply the
            ;; restriction around the current item, in the same way that
            ;; the previous fix for bug#35014 did.
            (error (line-beginning-position 2)))
        ;; Expand every line until the end of the restriction.
        (while (zerop (progn
                        ;; Assume that the line will expand and try to
                        ;; expand it.
                        (speedbar-expand-line arg)
                        ;; Moving forwards will be moving into the
                        ;; expanded lists if one opened, or moving to a
                        ;; sibling or end of restriction if there was no
                        ;; expansion.
                        (forward-line 1))))))
    (dframe-message "Expanding all descendants...done")
    ;; Reposition point to match the previous behavior.
    (speedbar-position-cursor-on-line))

> Also, this comment in the old code bothers me:
>
>> -    ;; Now, inside the area expanded here, expand all subnodes of
>> -    ;; the same descendant type.
>
> What does it mean by "the same descendant type", and how does the old
> and the new code make sure they expand only those descendants?

I don't know what it means by "type" because the code only deals with
siblings and children.  I think it means depth-first expansion of all
siblings.

The old code pre-bug#35014 did not ensure that it only expanded
descendants and just ran until the end of the buffer.

The old code with the fix for bug#35014 narrowed each item recursively
with the narrowing around the top level preventing a top-level sibling
being reached.

The new code just sets up the narrowing once around the top-level item
and then effectively runs the same expansion logic but without the item
look and message output.  The messages were being generated by calling
speedbar-item-info, and I cannot see how calling that repeatedly during
expansion is required when someone can just click the nodes open with
the mouse and also skip those calls.

I can re-send the patch with additional comments (more similar to the
above) if that helps.

Thanks,
Morgan

-- 
Morgan Willcock

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

[Morgan Willcock]

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

Morgan Willcock <morgan@ice9.digital> writes:

> The old code with the fix for bug#35014 narrowed each item recursively
> with the narrowing around the top level preventing a top-level sibling
> being reached.

The change that was made in bug#35014 looks like it broke the expansion
when the item was already partially expanded, so attached is a modified
version of the patch that completely removes the narrowing-per-item
approach and also includes more comments.

Thanks,
Morgan

-- 
Morgan Willcock

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Rewrite-speedbar-expansion-for-all-descendants.patch --]
[-- Type: text/x-diff, Size: 3563 bytes --]

From aa17e562b9844a50b8b01777c83830d3c4ead963 Mon Sep 17 00:00:00 2001
From: Morgan Willcock <morgan@ice9.digital>
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.  The
narrowing per item introduced by the fix for bug#35014 is
removed because it prevented expanded descendant items when the
top-level item was already expanded.

* 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.  Fix expansion of descendants where the top-level
item was already expanded.
---
 lisp/speedbar.el | 45 ++++++++++++++++++++++++++++++---------------
 1 file changed, 30 insertions(+), 15 deletions(-)

diff --git a/lisp/speedbar.el b/lisp/speedbar.el
index c13c977938b..723a5595854 100644
--- a/lisp/speedbar.el
+++ b/lisp/speedbar.el
@@ -3172,21 +3172,36 @@ 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 to ensure that later sibling
+        ;; items will not be entered.
+        (line-beginning-position)
+        (condition-case nil
+            (save-excursion
+              (speedbar-restricted-move 1)
+              ;; Use the line beginning position of the next sibling
+              ;; item to apply the restriction.
+              (line-beginning-position))
+          ;; This was the last sibling item so just apply the
+          ;; restriction to the end of the buffer.  This fixes the
+          ;; change applied in bug#35014 which prevented the top-level
+          ;; item from having its descendants expanded if it was already
+          ;; expanded.
+          (error (point-max)))
+      ;; Expand every line until the end of the restriction is reached.
+      (while (zerop (progn
+                      ;; Assume that the line will expand and try to
+                      ;; expand it.
+                      (speedbar-expand-line arg)
+                      ;; Moving forwards will be moving into the
+                      ;; expanded lists if one opened, into an already
+                      ;; expanded list if it was already open, to a
+                      ;; sibling, or to the end of restriction.
+                      (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

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

[Morgan Willcock]

Morgan Willcock <morgan@ice9.digital> writes:

> The change that was made in bug#35014 looks like it broke the expansion
> when the item was already partially expanded, so attached is a modified
> version of the patch that completely removes the narrowing-per-item
> approach and also includes more comments.

Unfortunately the narrowing trick causes problems in some situations,
either the previous way from bug#35014 or using the result of point-max
(either too few entries or expanded to too many).

I'll try to an alternative way to move through the entries.

-- 
Morgan Willcock