Repository: neovim
Issue: regexpengine=1 slow in RestructuredText Files
Labels: performance,bug-vim,syntax

<!-- Before reporting: search existing issues and check the FAQ. -->

- `nvim --version`:

  ```
  NVIM v0.4.4
  Build type: Gentoo
  Lua 5.1
  Compilation: /usr/bin/x86_64-pc-linux-gnu-gcc -O2 -pipe -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=1 -Wall -Wextra -pedantic -Wno-unused-parameter -Wstrict-prototypes -std=gnu99 -Wshadow -Wconversion -Wmissing-prototypes -Wimplicit-fallthrough -Wvla -fstack-protector-strong -fno-common -fdiagnostics-color=always -DINCLUDE_GENERATED_DECLARATIONS -D_GNU_SOURCE -DNVIM_MSGPACK_HAS_FLOAT32 -DNVIM_UNIBI_HAS_VAR_FROM -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/config -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4/src -I/usr/include -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/src/nvim/auto -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/include
  Compiled by portage@localhost

  Features: +acl +iconv +tui
  See ":help feature-compile"

     system vimrc file: "/etc/vim/sysinit.vim"
    fall-back for $VIM: "/usr/share/nvim"

  Run :checkhealth for more info
  ```

- Operating system/version: Gentoo Linux `x86_64`, up to date.
- Terminal name/version: `kitty` 0.20.3 running `tmux` 3.1c
- `$TERM`: `screen-256color`

<!--
If this report is about different behaviour between Nvim and Vim, make sure to
read `:h vim-differences` first. Otherwise remove the next line.
-->
[ ] `vim -u DEFAULTS` (version: 8.2) behaves differently

`vim` version info:

```
VIM - Vi IMproved 8.2 (2019 Dec 12, compiled Jun  1 2021 22:57:11)
Included patches: 1-814
Modified by Gentoo-8.2.0814-r100
Compiled by gavin@localhost
Huge version without GUI.  Features included (+) or not (-):
+acl               -farsi             +mouse_sgr         +tag_binary
+arabic            +file_in_path      -mouse_sysmouse    -tag_old_static
+autocmd           +find_in_path      +mouse_urxvt       -tag_any_white
+autochdir         +float             +mouse_xterm       -tcl
-autoservername    +folding           +multi_byte        +termguicolors
-balloon_eval      -footer            +multi_lang        -terminal
+balloon_eval_term +fork()            -mzscheme          +terminfo
-browse            +gettext           +netbeans_intg     +termresponse
++builtin_terms    -hangul_input      +num64             +textobjects
+byte_offset       +iconv             +packages          +textprop
+channel           +insert_expand     +path_extra        +timers
+cindent           +ipv6              -perl              +title
+clientserver      +job               +persistent_undo   -toolbar
+clipboard         +jumplist          +popupwin          +user_commands
+cmdline_compl     +keymap            +postscript        +vartabs
+cmdline_hist      +lambda            +printer           +vertsplit
+cmdline_info      +langmap           +profile           +virtualedit
+comments          +libcall           -python            +visual
+conceal           +linebreak         -python3           +visualextra
+cryptv            +lispindent        +quickfix          +viminfo
-cscope            +listcmds          +reltime           +vreplace
+cursorbind        +localmap          +rightleft         +wildignore
+cursorshape       -lua               -ruby              +wildmenu
+dialog_con        +menu              +scrollbind        +windows
+diff              +mksession         +signs             +writebackup
+digraphs          +modify_fname      +smartindent       +X11
-dnd               +mouse             -sound             +xfontset
-ebcdic            -mouseshape        +spell             -xim
+emacs_tags        +mouse_dec         +startuptime       -xpm
+eval              +mouse_gpm         +statusline        +xsmp_interact
+ex_extra          -mouse_jsbterm     -sun_workshop      +xterm_clipboard
+extra_search      +mouse_netterm     +syntax            -xterm_save
   system vimrc file: "/etc/vim/vimrc"
     user vimrc file: "$HOME/.vimrc"
 2nd user vimrc file: "~/.vim/vimrc"
      user exrc file: "$HOME/.exrc"
       defaults file: "$VIMRUNTIME/defaults.vim"
  fall-back for $VIM: "/usr/share/vim"
Compilation: x86_64-pc-linux-gnu-gcc -c -I. -Iproto -DHAVE_CONFIG_H     -O2 -pipe -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=1
Linking: x86_64-pc-linux-gnu-gcc   -Wl,-O1 -L/usr/local/lib -Wl,--as-needed -o vim    -lSM -lICE -lXpm -lXt -lX11 -lXdmcp -lSM -lICE  -lm -ltinfo -lelf  -lacl -lattr -lgpm -ldl
```

### Steps to reproduce using `nvim -u NORC`

```
nvim -u NORC
# Alternative for shell-related problems:
# env -i TERM=ansi-256color "$(which nvim)"
:set regexpengine=1
:e <location_of_main.rst_in_Actual_Behavior_below>
:570
o<BS>* Pointers should not be typed (
```

### Actual behaviour

When opening the file that can be found at <https://git.yzena.com/Yzena/Yc/src/branch/master/docs/yvm/design/main.rst>, Neovim takes several seconds to render the file, eventually spitting out the message:

```
'redrawtime' exceeded, syntax highlighting disabled
```

If you go down to the bottom of the file, just above the line:

```
.. toctree::
```

on line 570, insert a new line, and type:

```
* Pointers should not be typed (
```

Neovim freezes when trying to type the `(`.

When I profiled the problem with the procedure recommended [here](https://stackoverflow.com/questions/12213597/how-to-see-which-plugins-are-making-vim-slow/12216578#12216578), and when using the reproducer with `nvim -u NORC` above, I got the following in my `profile.log`:

```
FUNCTIONS SORTED ON SELF TIME
count  total (s)   self (s)  function
   66            366.269548  <SNR>12_Highlight_Matching_Pair()
  591              0.000869  RstFold#GetRstFold()
   48              0.000693  <SNR>26_DefineOneInlineMarkup()
    6   0.001034   0.000342  <SNR>26_DefineInlineMarkup()
    1   0.000405   0.000326  <SNR>2_LoadFTPlugin()
    1   0.028966   0.000116  <SNR>5_SynSet()
    1   0.000102   0.000063  <SNR>3_LoadIndent()
    1              0.000057  GetRSTIndent()
    1              0.000030  <SNR>13_LocalBrowse()
```

which obviously shows `73_Highlight_Matching_Pair()` as the problem.

When finding `Highlight_Matching_Pair()` in `profile.log`, I see this:

```
FUNCTION  <SNR>12_Highlight_Matching_Pair()
    Defined: /usr/share/nvim/runtime/plugin/matchparen.vim line 39
Called 66 times
Total time: 366.269548
 Self time: 366.269548

count  total (s)   self (s)
                              " Remove any previous match.
   66              0.000335   if exists('w:paren_hl_on') && w:paren_hl_on
                                silent! call matchdelete(3)
                                let w:paren_hl_on = 0
   66              0.000058   endif
                            
                              " Avoid that we remove the popup menu.
                              " Return when there are no colors (looks like the cursor jumps).
   66              0.000207   if pumvisible() || (&t_Co < 8 && !has("gui_running"))
                                return
   66              0.000023   endif
                            
                              " Get the character under the cursor and check if it's in 'matchpairs'.
   66              0.000153   let c_lnum = line('.')
   66              0.000114   let c_col = col('.')
   66              0.000060   let before = 0
                            
   66              0.000134   let text = getline(c_lnum)
   66              0.000758   let matches = matchlist(text, '\(.\)\=\%'.c_col.'c\(.\=\)')
   66              0.000096   if empty(matches)
                                let [c_before, c] = ['', '']
   66              0.000036   else
   66              0.000180     let [c_before, c] = matches[1:2]
   66              0.000027   endif
   66              0.000369   let plist = split(&matchpairs, '.\zs[:,]')
   66              0.000144   let i = index(plist, c)
   66              0.000054   if i < 0
                                " not found, in Insert mode try character before the cursor
   65              0.000166     if c_col > 1 && (mode() == 'i' || mode() == 'R')
   62              0.000111       let before = strlen(c_before)
   62              0.000060       let c = c_before
   62              0.000097       let i = index(plist, c)
   65              0.000026     endif
   65              0.000046     if i < 0
                                  " not found, nothing to do
   63              0.000042       return
    2              0.000001     endif
    3              0.000001   endif
                            
                              " Figure out the arguments for searchpairpos().
    3              0.000003   if i % 2 == 0
    3              0.000003     let s_flags = 'nW'
    3              0.000005     let c2 = plist[i + 1]
                              else
                                let s_flags = 'nbW'
                                let c2 = c
                                let c = plist[i - 1]
    3              0.000001   endif
    3              0.000003   if c == '['
                                let c = '\['
                                let c2 = '\]'
    3              0.000001   endif
                            
                              " Find the match.  When it was just before the cursor move it there for a
                              " moment.
    3              0.000002   if before > 0
    2              0.000006     let has_getcurpos = exists("*getcurpos")
    2              0.000002     if has_getcurpos
                                  " getcurpos() is more efficient but doesn't exist before 7.4.313.
    2              0.000005       let save_cursor = getcurpos()
                                else
                                  let save_cursor = winsaveview()
    2              0.000001     endif
    2              0.000006     call cursor(c_lnum, c_col - before)
    3              0.000001   endif
                            
    3              0.000017   if !has("syntax") || !exists("g:syntax_on")
                                let s_skip = "0"
    3              0.000001   else
                                " Build an expression that detects whether the current cursor position is
                                " in certain syntax types (string, comment, etc.), for use as
                                " searchpairpos()'s skip argument.
                                " We match "escape" for special items, such as lispEscapeSpecial.
    3              0.000008     let s_skip = '!empty(filter(map(synstack(line("."), col(".")), ''synIDattr(v:val, "name")''), ' . '''v:val =~? "string\\|character\\|singlequote\\|escape\\|comment"''))'
                                " If executing the expression determines that the cursor is currently in
                                " one of the syntax types, then we want searchpairpos() to find the pair
                                " within those syntax types (i.e., not skip).  Otherwise, the cursor is
                                " outside of the syntax types and s_skip should keep its value so we skip
                                " any matching pair inside the syntax types.
                                " Catch if this throws E363: pattern uses more memory than 'maxmempattern'.
    3              0.000003     try
    3              0.000820       execute 'if ' . s_skip . ' | let s_skip = "0" | endif'
                                catch /^Vim\%((\a\+)\)\=:E363/
                                  " We won't find anything, so skip searching, should keep Vim responsive.
                                  return
    3              0.000002     endtry
    3              0.000001   endif
                            
                              " Limit the search to lines visible in the window.
    3              0.000007   let stoplinebottom = line('w$')
    3              0.000007   let stoplinetop = line('w0')
    3              0.000003   if i % 2 == 0
    3              0.000004     let stopline = stoplinebottom
                              else
                                let stopline = stoplinetop
    3              0.000001   endif
                            
                              " Limit the search time to 300 msec to avoid a hang on very long lines.
                              " This fails when a timeout is not supported.
    3              0.000006   if mode() == 'i' || mode() == 'R'
    2              0.000007     let timeout = exists("b:matchparen_insert_timeout") ? b:matchparen_insert_timeout : g:matchparen_insert_timeout
    1              0.000000   else
    1              0.000003     let timeout = exists("b:matchparen_timeout") ? b:matchparen_timeout : g:matchparen_timeout
    3              0.000001   endif
    3              0.000001   try
    3            366.264369     let [m_lnum, m_col] = searchpairpos(c, '', c2, s_flags, s_skip, stopline, timeout)
                              catch /E118/
                                " Can't use the timeout, restrict the stopline a bit more to avoid taking
                                " a long time on closed folds and long lines.
                                " The "viewable" variables give a range in which we can scroll while
                                " keeping the cursor at the same position.
                                " adjustedScrolloff accounts for very large numbers of scrolloff.
                                let adjustedScrolloff = min([&scrolloff, (line('w$') - line('w0')) / 2])
                                let bottom_viewable = min([line('$'), c_lnum + &lines - adjustedScrolloff - 2])
                                let top_viewable = max([1, c_lnum-&lines+adjustedScrolloff + 2])
                                " one of these stoplines will be adjusted below, but the current values are
                                " minimal boundaries within the current window
                                if i % 2 == 0
                                  if has("byte_offset") && has("syntax_items") && &smc > 0
                            	let stopbyte = min([line2byte("$"), line2byte(".") + col(".") + &smc * 2])
                            	let stopline = min([bottom_viewable, byte2line(stopbyte)])
                                  else
                            	let stopline = min([bottom_viewable, c_lnum + 100])
                                  endif
                                  let stoplinebottom = stopline
                                else
                                  if has("byte_offset") && has("syntax_items") && &smc > 0
                            	let stopbyte = max([1, line2byte(".") + col(".") - &smc * 2])
                            	let stopline = max([top_viewable, byte2line(stopbyte)])
                                  else
                            	let stopline = max([top_viewable, c_lnum - 100])
                                  endif
                                  let stoplinetop = stopline
                                endif
                                let [m_lnum, m_col] = searchpairpos(c, '', c2, s_flags, s_skip, stopline)
    3              0.000002   endtry
                            
    3              0.000004   if before > 0
    2              0.000002     if has_getcurpos
    2              0.000008       call setpos('.', save_cursor)
                                else
                                  call winrestview(save_cursor)
    2              0.000001     endif
    3              0.000001   endif
                            
                              " If a match is found setup match highlighting.
    3              0.000004   if m_lnum > 0 && m_lnum >= stoplinetop && m_lnum <= stoplinebottom 
                                if exists('*matchaddpos')
                                  call matchaddpos('MatchParen', [[c_lnum, c_col - before], [m_lnum, m_col]], 10, 3)
                                else
                                  exe '3match MatchParen /\(\%' . c_lnum . 'l\%' . (c_col - before) . 'c\)\|\(\%' . m_lnum . 'l\%' . m_col . 'c\)/'
                                endif
                                let w:paren_hl_on = 1
    3              0.000001   endif

```

So it appears that `searchpairpos()` may be the problem.

In addition, editing RestructuredText files in Neovim just feels slow, and when profiling the slow editing, nothing really stands out.

### Expected behaviour

Instant, or near instant, editing of RestructuredText files.

### Other

I would love to help fix this, but I am not familiar enough with Neovim's code to help. If I can get some pointers, I can try to track it down further and fix it.