GNU bug report logs - #73533
[PATCH] Rewrite speedbar expansion for all descendants

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 73533 in the body.
You can then email your comments to 73533 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: bug-gnu-emacs <at> gnu.org
Subject: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sat, 28 Sep 2024 20:05:26 +0100

[Message part 1 (text/plain, inline)]

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'

[0001-Rewrite-speedbar-expansion-for-all-descendants.patch (text/patch, attachment)]

Message #8 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Morgan Willcock <morgan <at> ice9.digital>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sun, 29 Sep 2024 07:46:08 +0300

> From: Morgan Willcock <morgan <at> 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?

Message #11 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sun, 29 Sep 2024 10:52:07 +0100

Eli Zaretskii <eliz <at> 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

Message #16 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Mon, 30 Sep 2024 10:03:18 +0100

[Message part 1 (text/plain, inline)]

Morgan Willcock <morgan <at> 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

[0001-Rewrite-speedbar-expansion-for-all-descendants.patch (text/x-diff, attachment)]

Message #19 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Mon, 30 Sep 2024 19:28:12 +0100

Morgan Willcock <morgan <at> 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

Message #22 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Tue, 08 Oct 2024 19:36:06 +0100

[Message part 1 (text/plain, inline)]

Attached is a patch for a replacement function and an additional patch
which adds tests for expanding all descendants.

I couldn't see a direct way to test a Speedbar without creating a frame,
and because the Speedbar code doesn't implement any type of hierarchy
itself I've used eieio-speedbar to make something minimal to test.

Each test runs by converting a list of strings into objects which
implement a Speedbar display, making state changes for the functions
being tested, and then converting the objects back into strings - this
was the simplest way I could find to create a reusable interface for
tests.  The conversion back to a string is customizable to allow
whatever state change is under test to be represented.

If the tests are problematic or considered too complicated, perhaps they
can just be used to test the current function and the replacement
function and not committed.  The current function fails 3/9 tests.

-- 
Morgan Willcock

[0001-Rewrite-speedbar-expansion-for-all-descendants.patch (text/x-diff, attachment)]

[0002-Add-initial-Speedbar-tests.patch (text/x-diff, attachment)]

Message #25 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Morgan Willcock <morgan <at> ice9.digital>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sat, 19 Oct 2024 10:42:41 +0300

> From: Morgan Willcock <morgan <at> ice9.digital>
> Cc: 73533 <at> debbugs.gnu.org
> Date: Tue, 08 Oct 2024 19:36:06 +0100
> 
> Attached is a patch for a replacement function and an additional patch
> which adds tests for expanding all descendants.
> 
> I couldn't see a direct way to test a Speedbar without creating a frame,
> and because the Speedbar code doesn't implement any type of hierarchy
> itself I've used eieio-speedbar to make something minimal to test.
> 
> Each test runs by converting a list of strings into objects which
> implement a Speedbar display, making state changes for the functions
> being tested, and then converting the objects back into strings - this
> was the simplest way I could find to create a reusable interface for
> tests.  The conversion back to a string is customizable to allow
> whatever state change is under test to be represented.
> 
> If the tests are problematic or considered too complicated, perhaps they
> can just be used to test the current function and the replacement
> function and not committed.  The current function fails 3/9 tests.

Thanks, I installed these patches on master.

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?

Message #28 received at 73533 <at> debbugs.gnu.org (full text, mbox):

From: Morgan Willcock <morgan <at> ice9.digital>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73533 <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sat, 19 Oct 2024 18:30:13 +0100

Eli Zaretskii <eliz <at> gnu.org> 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.

-- 
Morgan Willcock

Message #33 received at 73533-done <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Morgan Willcock <morgan <at> ice9.digital>
Cc: 73533-done <at> debbugs.gnu.org
Subject: Re: bug#73533: [PATCH] Rewrite speedbar expansion for all descendants
Date: Sat, 19 Oct 2024 20:41:37 +0300

> From: Morgan Willcock <morgan <at> ice9.digital>
> Cc: 73533 <at> debbugs.gnu.org
> Date: Sat, 19 Oct 2024 18:30:13 +0100
> 
> Eli Zaretskii <eliz <at> gnu.org> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.