Subject: Re: bug#72977: 28.2; DOS in Shell-script mode

From: Stefan Monnier <[email-masked]>
Date: Wed, 04 Sep 2024 08:53:55 -0400

>> echo in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in
>> 
>> After about 20 'in's, things slow down noticeably, and I can't get to 30 without it hanging.
>
> The profile is below.  Maybe Stefan (CC'ed) has some comments or
> suggestions.
>
>        36361  58% - timer-event-handler
>        36361  58%  - apply
>        36361  58%   - show-paren-function
>        36361  58%    - #<advice 1DA>
>        36361  58%     - apply
>        36361  58%      - smie--matching-block-data
>        36359  58%       - smie--opener/closer-at-point
>        36068  57%        - sh-smie-sh-forward-token
>        23841  38%         - sh-smie--sh-keyword-p
>        23841  38%          - sh-smie--sh-keyword-in/do-p
>        23841  38%           - sh-smie-sh-backward-token
>        23837  38%            - sh-smie--sh-keyword-p
>        23837  38%             - sh-smie--sh-keyword-in/do-p
>        23837  38%              - sh-smie-sh-backward-token
>        23805  38%               - sh-smie--sh-keyword-p
>        23801  38%                - sh-smie--sh-keyword-in/do-p
>        23793  38%                 - sh-smie-sh-backward-token
>        23685  38%                  - sh-smie--sh-keyword-p
[...]

Hmm... indeed, in order to decide whether a given `in` is a keyword
rather than just some command's argument, we need to look back, so we
probably have an O(N²) situation here, where we walk backward over all
the `in`s in order to decide whether the last one is a keyword.  Then we
do the same starting from the "last but one" (because the check for
keyword-p was only made to decide how to skip that last token), etc...

In theory we could do it more efficiently by integrating better the
keyword-p check and the navigation to the beginning of a command, but it
requires a different structure than the one we're using.

Another solution is to use a cache (which could simply memoize the
output of `sh-smie--sh-keyword-p`) which we could flush from
`after-change-functions`.

Yet another (more ad-hoc) approach might be to try and keep track of the
nesting, and let `sh-smie--sh-keyword-p` return nil when we reach
a nesting of say 2 (at least for `in` I can't think of a piece of code
where the 3rd (or subsequent) `in` can be a keyword).

        Stefan