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

[Morgan Willcock <morgan@ice9.digital>]

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