commit bdcfca1e5ce10b571d4ecacc9e2c3527f54fe226
parent efcc3f1fa5f27c5697b4f3ed44741ac1754c3b63
Author: Henry Qin <root@hq6.me>
Date: Mon, 18 Mar 2019 11:33:11 -0700
Merge branch 'lyokha-dev' into dev. Closes #47.
This PR optimizes large table reformatting to only look at a subset of
rows.
Diffstat:
5 files changed, 329 insertions(+), 76 deletions(-)
diff --git a/DesignNotes.wiki b/DesignNotes.wiki
@@ -3,3 +3,185 @@
This file is meant to document design decisions and algorithms inside vimwiki
which are too large for code comments, and not necessarily interesting to
users. Please create a new section to document each behavior.
+
+== Formatting tables ==
+
+In vimwiki, formatting tables occurs dynamically, when navigating between cells
+and adding new rows in a table in the Insert mode, or statically, when pressing
+`gqq` or `gqw` (which are mappings for commands `VimwikiTableAlignQ` and
+`VimwikiTableAlignW` respectively) in the Normal mode. It also triggers when
+leaving Insert mode, provided variable `g:vimwiki_table_auto_fmt` is set. In
+this section, the original and the newer optimized algorithms of table
+formatting will be described and compared.
+
+=== The older table formatting algorithm and why this is not optimal ===
+
+Let's consider a simple example. Open a new file, say _tmp.wiki_, and create a
+new table with command `VimwikiTable`. This should create a blank table.
+
+{{{
+| | | | | |
+|---|---|---|---|---|
+| | | | | |
+}}}
+
+Let's put the cursor in the first header column of the table, enter the Insert
+mode and type a name, say _Col1_. Then press _Tab_: the cursor will move to the
+second column of the header and the table will get aligned (in the context of
+the table formatting story, words _aligned_ and _formatted_ are considered as
+synonyms). Now the table looks as in the following snippet.
+
+{{{
+| Col1 | | | | |
+|------|---|---|---|---|
+| | | | | |
+}}}
+
+Then, when moving cursor to the first data row (i.e. to the third line of the
+table below the separator line) and typing anything here and there while
+navigating using _Tab_ or _Enter_ (pressing this creates a new row below the
+current row), the table shall keep formatting. Below is a result of such a
+random edit.
+
+{{{
+| Col1 | | | | |
+|------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| | | | | New data |
+}}}
+
+The lowest row gets aligned when leaving the Insert mode. Let's copy _Data1_
+(using `viwy` or another keystroke) and paste it (using `p`) in the second data
+row of the first column. Now the table looks mis-aligned (as we did not enter
+the Insert mode).
+
+{{{
+| Col1 | | | | |
+|------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| Data1 | | | | New data |
+}}}
+
+This is not a big problem though, because we can put the cursor at _any_ place
+in the table and press `gqq`: the table will get aligned.
+
+{{{
+| Col1 | | | | |
+|-------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| Data1 | | | | New data |
+}}}
+
+Now let's make real problems! Move the cursor to the lowest row and copy it
+with `yy`. Then 500-fold paste it with `500p`. Now the table very long. Move
+the cursor to the lowest row (by pressing `G`), enter the Insert mode, and try
+a new random editing session by typing anything in cells with _Tab_ and _Enter_
+navigation interleaves. The editing got painfully slow, did not?
+
+The reason of the slowing down is the older table formatting algorithm. Every
+time _Tab_ or _Enter_ get pressed down, all rows in the table get visited to
+calculate a new alignment. Moreover, by design it may happen even more than
+once per one press!
+
+{{{vim
+function! s:kbd_create_new_row(cols, goto_first)
+ let cmd = "\<ESC>o".s:create_empty_row(a:cols)
+ let cmd .= "\<ESC>:call vimwiki#tbl#format(line('.'))\<CR>"
+ let cmd .= "\<ESC>0"
+ if a:goto_first
+ let cmd .= ":call search('\\(".s:rxSep()."\\)\\zs', 'c', line('.'))\<CR>"
+ else
+ let cmd .= (col('.')-1)."l"
+ let cmd .= ":call search('\\(".s:rxSep()."\\)\\zs', 'bc', line('.'))\<CR>"
+ endif
+ let cmd .= "a"
+
+ return cmd
+endfunction
+}}}
+
+Function `s:kbd_create_new_row()` is called when _Tab_ or _Enter_ get pressed.
+Formatting of the whole table happens in function `vimwiki#tbl#format()`. But
+remember that leaving the Insert mode triggers re-formatting of a table when
+variable `g:vimwiki_table_auto_fmt` is set. This means that formatting of the
+whole table is called on all those multiple interleaves between the Insert and
+the Normal mode in `s:kbd_create_new_row` (notice `\<ESC>`, `o`, etc.).
+
+=== The newer table formating algorithm ===
+
+The newer algorithm was introduced to struggle against performance issues when
+formatting large tables.
+
+Let's take the table from the previous example in an intermediate state.
+
+{{{
+| Col1 | | | | |
+|------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| Data1 | | | | New data |
+}}}
+
+Then move the cursor to the first data row, copy it with `yy`, go down to the
+mis-aligned line, and press `5p`. Now we have a slightly bigger mis-aligned
+table.
+
+{{{
+| Col1 | | | | |
+|------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| Data1 | | | | New data |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+}}}
+
+Go down to the lowest, the 7th, data row and press `gq1`. Nothing happened.
+Let's go to the second or the third data row and press `gq1` once again. Now
+the table gets aligned. Let's undo formatting with `u`, go to the fourth row,
+and press `gq1`. Now the table should look like in the following snippet.
+
+{{{
+| Col1 | | | | |
+|------|-------|---|-------|----------|
+| | Data1 | | Data2 | |
+| Data1 | | | | New data |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+| | Data1 | | Data2 | |
+}}}
+
+What a peculiar command! Does using it make any sense? Not much, honestly.
+Except it shows how the newer optimized table formatting algorithm works in the
+Insert mode.
+
+Indeed, the newer table formatting algorithm introduces a _viewport_ on a table.
+Now, when pressing _Tab_ or _Enter_ in the Insert mode, only a small part of
+rows are checked for possible formatting: two rows above the current line and
+the current line itself (the latter gets preliminary shrunk with function
+`s:fmt_row()`). If all three lines in the viewport are of the same length, then
+nothing happens (case 1 in the example). If the second or the shrunk current
+line is longer then the topmost line in the viewport, then the algorithm falls
+back to the older formatting algorithm and the whole table gets aligned
+(case 2). If the topmost line in the viewport is longer than the second
+and the shrunk current line, then the two lowest lines get aligned according to
+the topmost line (case 3).
+
+Performance of the newer formatting algorithm should not depend on the height
+of the table. The newer algorithm should also be consistent with respect to
+user editing experience. Indeed, as soon as a table should normally be edited
+row by row from the top to the bottom, dynamic formatting should be both fast
+(watching only three rows in a table, re-formatting only when the shrunk
+current row gets longer than any of the two rows above) and eager (a table
+should look formatted on every press on _Tab_ and _Enter_). However, the newer
+algorithm differs from the older algorithm when starting editing a mis-aligned
+table in an area where mis-aligned rows do not get into the viewport: in this
+case the newer algorithm will format the table partly (in the rows of the
+viewport) until one of the being edited cells grows in length to a value big
+enough to trigger the older algorithm and the whole table gets aligned. When
+partial formatting is not desirable, the whole table can be formatted by
+pressing `gqq` in the Normal mode.
+
diff --git a/autoload/vimwiki/tbl.vim b/autoload/vimwiki/tbl.vim
@@ -140,56 +140,62 @@ function! s:create_row_sep(cols)
endfunction
-function! vimwiki#tbl#get_cells(line)
+function! vimwiki#tbl#get_cells(line, ...)
let result = []
- let cell = ''
- let quote = ''
let state = 'NONE'
+ let cell_start = 0
+ let quote_start = 0
+ let len = strlen(a:line) - 1
" 'Simple' FSM
- for idx in range(strlen(a:line))
- " The only way I know Vim can do Unicode...
- let ch = a:line[idx]
- if state ==# 'NONE'
- if ch == '|'
- let state = 'CELL'
- endif
- elseif state ==# 'CELL'
- if ch == '[' || ch == '{'
- let state = 'BEFORE_QUOTE_START'
- let quote = ch
- elseif ch == '|'
- call add(result, vimwiki#u#trim(cell))
- let cell = ""
- else
- let cell .= ch
- endif
- elseif state ==# 'BEFORE_QUOTE_START'
- if ch == '[' || ch == '{'
- let state = 'QUOTE'
- let quote .= ch
- else
- let state = 'CELL'
- let cell .= quote.ch
- let quote = ''
- endif
- elseif state ==# 'QUOTE'
- if ch == ']' || ch == '}'
- let state = 'BEFORE_QUOTE_END'
- endif
- let quote .= ch
- elseif state ==# 'BEFORE_QUOTE_END'
- if ch == ']' || ch == '}'
- let state = 'CELL'
+ while state != 'CELL'
+ if quote_start != 0 && state != 'CELL'
+ let state = 'CELL'
+ endif
+ for idx in range(quote_start, len)
+ " The only way I know Vim can do Unicode...
+ let ch = a:line[idx]
+ if state ==# 'NONE'
+ if ch == '|'
+ let cell_start = idx + 1
+ let state = 'CELL'
+ endif
+ elseif state ==# 'CELL'
+ if ch == '[' || ch == '{'
+ let state = 'BEFORE_QUOTE_START'
+ let quote_start = idx
+ elseif ch == '|'
+ let cell = strpart(a:line, cell_start, idx - cell_start)
+ if a:0 && a:1
+ let cell = substitute(cell, '^ \(.*\) $', '\1', '')
+ else
+ let cell = vimwiki#u#trim(cell)
+ endif
+ call add(result, cell)
+ let cell_start = idx + 1
+ endif
+ elseif state ==# 'BEFORE_QUOTE_START'
+ if ch == '[' || ch == '{'
+ let state = 'QUOTE'
+ let quote_start = idx
+ else
+ let state = 'CELL'
+ endif
+ elseif state ==# 'QUOTE'
+ if ch == ']' || ch == '}'
+ let state = 'BEFORE_QUOTE_END'
+ endif
+ elseif state ==# 'BEFORE_QUOTE_END'
+ if ch == ']' || ch == '}'
+ let state = 'CELL'
+ endif
endif
- let cell .= quote.ch
- let quote = ''
+ endfor
+ if state == 'NONE'
+ break
endif
- endfor
+ endwhile
- if cell.quote != ''
- call add(result, vimwiki#u#trim(cell.quote, '|'))
- endif
return result
endfunction
@@ -199,7 +205,7 @@ function! s:col_count(lnum)
endfunction
-function! s:get_indent(lnum)
+function! s:get_indent(lnum, depth)
if !s:is_table(getline(a:lnum))
return
endif
@@ -214,50 +220,64 @@ function! s:get_indent(lnum)
break
endif
let lnum -= 1
+ if a:depth > 0 && lnum < a:lnum - a:depth
+ break
+ endif
endwhile
return indent
endfunction
-function! s:get_rows(lnum)
+function! s:get_rows(lnum, ...)
if !s:is_table(getline(a:lnum))
return
endif
- let upper_rows = []
- let lower_rows = []
+ let rows = []
let lnum = a:lnum - 1
- while lnum >= 1
+ let depth = a:0 > 0 ? a:1 : 0
+ let ldepth = 0
+ while lnum >= 1 && (depth == 0 || ldepth < depth)
let line = getline(lnum)
if s:is_table(line)
- call add(upper_rows, [lnum, line])
+ call insert(rows, [lnum, line])
else
break
endif
let lnum -= 1
+ let ldepth += 1
endwhile
- call reverse(upper_rows)
let lnum = a:lnum
while lnum <= line('$')
let line = getline(lnum)
if s:is_table(line)
- call add(lower_rows, [lnum, line])
+ if lnum == a:lnum
+ let cells = vimwiki#tbl#get_cells(line)
+ let clen = len(cells)
+ let max_lens = repeat([0], clen)
+ let aligns = repeat(['left'], clen)
+ let line = s:fmt_row(cells, max_lens, aligns, 0, 0)
+ endif
+ call add(rows, [lnum, line])
else
break
endif
+ if depth > 0
+ break
+ endif
let lnum += 1
endwhile
- return upper_rows + lower_rows
+ return rows
endfunction
-function! s:get_cell_aligns(lnum)
+function! s:get_cell_aligns(lnum, depth)
let aligns = {}
- for [lnum, row] in s:get_rows(a:lnum)
+ for [lnum, row] in s:get_rows(a:lnum, a:depth)
let found_separator = s:is_separator(row)
if found_separator
let cells = vimwiki#tbl#get_cells(row)
@@ -286,7 +306,8 @@ endfunction
function! s:get_cell_max_lens(lnum, ...)
let max_lens = {}
- for [lnum, row] in s:get_rows(a:lnum)
+ let rows = a:0 > 2 ? a:3 : s:get_rows(a:lnum)
+ for [lnum, row] in rows
if s:is_separator(row)
continue
endif
@@ -304,15 +325,38 @@ function! s:get_cell_max_lens(lnum, ...)
endfunction
-function! s:get_aligned_rows(lnum, col1, col2)
- let rows = s:get_rows(a:lnum)
- let startlnum = rows[0][0]
+function! s:get_aligned_rows(lnum, col1, col2, depth)
+ let rows = []
+ let startlnum = 0
let cells = []
- for [lnum, row] in rows
- call add(cells, vimwiki#tbl#get_cells(row))
- endfor
- let max_lens = s:get_cell_max_lens(a:lnum, cells, startlnum)
- let aligns = s:get_cell_aligns(a:lnum)
+ let max_lens = {}
+ let check_all = 1
+ if a:depth > 0
+ let rows = s:get_rows(a:lnum, a:depth)
+ let startlnum = rows[0][0]
+ let lrows = len(rows)
+ if lrows == a:depth + 1
+ let i = 1
+ for [lnum, row] in rows
+ call add(cells, vimwiki#tbl#get_cells(row, i != lrows - 1))
+ let i += 1
+ endfor
+ let max_lens = s:get_cell_max_lens(a:lnum, cells, startlnum, rows)
+ let fst_lens = s:get_cell_max_lens(a:lnum, cells, startlnum, rows[0:0])
+ let check_all = max_lens != fst_lens
+ endif
+ endif
+ if check_all
+ " all the table must be re-formatted
+ let rows = s:get_rows(a:lnum)
+ let startlnum = rows[0][0]
+ let cells = []
+ for [lnum, row] in rows
+ call add(cells, vimwiki#tbl#get_cells(row))
+ endfor
+ let max_lens = s:get_cell_max_lens(a:lnum, cells, startlnum, rows)
+ endif
+ let aligns = s:get_cell_aligns(a:lnum, a:depth)
let result = []
for [lnum, row] in rows
if s:is_separator(row)
@@ -419,7 +463,7 @@ endfunction
function! s:kbd_create_new_row(cols, goto_first)
let cmd = "\<ESC>o".s:create_empty_row(a:cols)
- let cmd .= "\<ESC>:call vimwiki#tbl#format(line('.'))\<CR>"
+ let cmd .= "\<ESC>:call vimwiki#tbl#format(line('.'), 2)\<CR>"
let cmd .= "\<ESC>0"
if a:goto_first
let cmd .= ":call search('\\(".s:rxSep()."\\)\\zs', 'c', line('.'))\<CR>"
@@ -455,8 +499,15 @@ endfunction
function! vimwiki#tbl#goto_next_col()
let curcol = virtcol('.')
let lnum = line('.')
- let newcol = s:get_indent(lnum)
- let max_lens = s:get_cell_max_lens(lnum)
+ let depth = 2
+ let newcol = s:get_indent(lnum, depth)
+ let rows = s:get_rows(lnum, depth)
+ let startlnum = rows[0][0]
+ let cells = []
+ for [lnum, row] in rows
+ call add(cells, vimwiki#tbl#get_cells(row, 1))
+ endfor
+ let max_lens = s:get_cell_max_lens(lnum, cells, startlnum, rows)
for cell_len in values(max_lens)
if newcol >= curcol-1
break
@@ -483,8 +534,15 @@ endfunction
function! vimwiki#tbl#goto_prev_col()
let curcol = virtcol('.')
let lnum = line('.')
- let newcol = s:get_indent(lnum)
- let max_lens = s:get_cell_max_lens(lnum)
+ let depth = 2
+ let newcol = s:get_indent(lnum, depth)
+ let rows = s:get_rows(lnum, depth)
+ let startlnum = rows[0][0]
+ let cells = []
+ for [lnum, row] in rows
+ call add(cells, vimwiki#tbl#get_cells(row, 1))
+ endfor
+ let max_lens = s:get_cell_max_lens(lnum, cells, startlnum, rows)
let prev_cell_len = 0
for cell_len in values(max_lens)
let delta = cell_len + 3 " +3 == 2 spaces + 1 separator |<space>...<space>
@@ -574,6 +632,8 @@ function! vimwiki#tbl#format(lnum, ...)
return
endif
+ let depth = a:0 == 1 ? a:1 : 0
+
if a:0 == 2
let col1 = a:1
let col2 = a:2
@@ -582,16 +642,19 @@ function! vimwiki#tbl#format(lnum, ...)
let col2 = 0
endif
- let indent = s:get_indent(a:lnum)
+ let indent = s:get_indent(a:lnum, depth)
if &expandtab
let indentstring = repeat(' ', indent)
else
let indentstring = repeat(' ', indent / &tabstop) . repeat(' ', indent % &tabstop)
endif
- for [lnum, row] in s:get_aligned_rows(a:lnum, col1, col2)
+ " getting N = depth last rows is enough for having been formatted tables
+ for [lnum, row] in s:get_aligned_rows(a:lnum, col1, col2, depth)
let row = indentstring.row
- call setline(lnum, row)
+ if getline(lnum) != row
+ call setline(lnum, row)
+ endif
endfor
let &tw = s:textwidth
@@ -634,9 +697,9 @@ function! vimwiki#tbl#create(...)
endfunction
-function! vimwiki#tbl#align_or_cmd(cmd)
+function! vimwiki#tbl#align_or_cmd(cmd, ...)
if s:is_table(getline('.'))
- call vimwiki#tbl#format(line('.'))
+ call call('vimwiki#tbl#format', [line('.')] + a:000)
else
exe 'normal! '.a:cmd
endif
diff --git a/doc/vimwiki.txt b/doc/vimwiki.txt
@@ -513,6 +513,12 @@ gqq Format table. If you made some changes to a table
or without swapping insert/normal modes this command
gww will reformat it.
+ *vimwiki_gq1* *vimwiki_gw1*
+gq1 Fast format table. The same as the previous, except
+ or that only a few lines above the current line are
+gw1 tested. If the alignment of the current line differs,
+ then the whole table gets reformatted.
+
*vimwiki_<A-Left>*
<A-Left> Move current table column to the left.
See |:VimwikiTableMoveColumnLeft|
diff --git a/ftplugin/vimwiki.vim b/ftplugin/vimwiki.vim
@@ -305,8 +305,8 @@ command! -buffer VimwikiListToggle call vimwiki#lst#toggle_list_item()
" table commands
command! -buffer -nargs=* VimwikiTable call vimwiki#tbl#create(<f-args>)
-command! -buffer VimwikiTableAlignQ call vimwiki#tbl#align_or_cmd('gqq')
-command! -buffer VimwikiTableAlignW call vimwiki#tbl#align_or_cmd('gww')
+command! -buffer -nargs=? VimwikiTableAlignQ call vimwiki#tbl#align_or_cmd('gqq', <f-args>)
+command! -buffer -nargs=? VimwikiTableAlignW call vimwiki#tbl#align_or_cmd('gww', <f-args>)
command! -buffer VimwikiTableMoveColumnLeft call vimwiki#tbl#move_column_left()
command! -buffer VimwikiTableMoveColumnRight call vimwiki#tbl#move_column_right()
@@ -584,6 +584,8 @@ endif
nnoremap <buffer> gqq :VimwikiTableAlignQ<CR>
nnoremap <buffer> gww :VimwikiTableAlignW<CR>
+nnoremap <buffer> gq1 :VimwikiTableAlignQ 2<CR>
+nnoremap <buffer> gw1 :VimwikiTableAlignW 2<CR>
if !hasmapto('<Plug>VimwikiTableMoveColumnLeft')
nmap <silent><buffer> <A-Left> <Plug>VimwikiTableMoveColumnLeft
endif
diff --git a/plugin/vimwiki.vim b/plugin/vimwiki.vim
@@ -261,7 +261,7 @@ augroup vimwiki
" Format tables when exit from insert mode. Do not use textwidth to
" autowrap tables.
if vimwiki#vars#get_global('table_auto_fmt')
- exe 'autocmd InsertLeave *'.s:ext.' call vimwiki#tbl#format(line("."))'
+ exe 'autocmd InsertLeave *'.s:ext.' call vimwiki#tbl#format(line("."), 2)'
exe 'autocmd InsertEnter *'.s:ext.' call vimwiki#tbl#reset_tw(line("."))'
endif
if vimwiki#vars#get_global('folding') =~? ':quick$'