[RFC] Hide list implementation #7708

ZyX-I · 2017-12-10T00:44:29Z

Huge refactoring aiming at plaing with list implementation (specifically, replacing list with either growarray or the like or kvec and running benchmarks). To do that all implementation-specific code should end up in eval/typval.[ch].

Should solve a bunch of issues from #4615 in process, simply because “NULL is an empty list” implementation detail gets hidden away.

Most of files, except for eval.c and eval/* were only processed by perl.

It is the same for other VAR_FIXED lists.

ZyX-I · 2017-12-11T07:46:15Z

Should be ready if CI succeeds. Not switching implementation in this PR yet, better to have first refactoring merged and then do some experimenting as it is going to be more subjective (specifically what benchmarks to perform). Note: after this merged any new code matching ->lv_ or ->li_ is invalid with a few exceptions regarding GC and eval/typval.

justinmk · 2017-12-11T07:59:08Z

Note: after this merged any new code matching ->lv_ or ->li_ is invalid with a few exceptions regarding GC and eval/typval.

Perhaps the linter could catch this?

oni-link · 2017-12-11T08:05:47Z

src/nvim/eval/typval.h

+
+/// Normalize index: that is, return either -1 or non-negative index
+///
+/// @param[in]  l  List to intex. Used to get length.


intex->index

[ci skip]

ZyX-I · 2017-12-16T11:32:08Z

If CI passes this should be ready, previous CI only failed trailing whitespace lint check.

ZyX-I · 2017-12-16T11:59:06Z

AppVeyor and QB succeeded.

ZyX-I · 2017-12-16T12:41:39Z

Travis failure looks unrelated:

missing:
provider/pythonx: Could not load Python 3:
/opt/pyenv/shims/python3 does not have the "neovim" module. :help provider-python
python3.7 not found in search path or not executable.
/opt/pyenv/shims/python3.6 does not exist: pyenv: python3.6: command not found

The `python3.6' command exists in these Python versions:
  3.6
  3.6.3


python3.5 not found in search path or not executable.
/usr/bin/python3.4 does not have the "neovim" module. :help provider-python
python3.3 not found in search path or not executable.
/opt/pyenv/shims/python is Python 2.7 and cannot provide Python 3.�[0m
�[1m�[31m[  ERROR   ]�[0m�[0m �[1m1�[0m error, listed below:
�[1m�[31m[  ERROR   ]�[0m�[0m �[36m...uild/neovim/neovim/test/functional/terminal/tui_spec.lua�[0m @ �[36m351�[0m: �[1mtui FocusGained/FocusLost in cmdline-mode�[0m
./test/functional/helpers.lua:269: 
retry() attempts: 2
./test/functional/ui/screen.lua:307: Row 2 did not match.
Expected:
  |{1: }                                                 |
  |*lost                                              |
  |gained                                            |
  |{4:~                                                 }|
  |{5:[No Name] [+]                                     }|
  |:                                                 |
  |{3:-- TERMINAL --}                                    |
Actual:
  |{1: }                                                 |
  |*gained                                            |
  |lost                                              |
  |gained                                            |
  |{5:[No Name] [+]                                     }|
  |:                                                 |
  |{3:-- TERMINAL --}                                    |

To print the expect() call that would assert the current screen state, use
screen:snapshot_util(). In case of non-deterministic failures, use
screen:redraw_debug() to show all intermediate screen states.  

stack traceback:
	./test/functional/helpers.lua:269: in function 'retry'
	...uild/neovim/neovim/test/functional/terminal/tui_spec.lua:358: in function <...uild/neovim/neovim/test/functional/terminal/tui_spec.lua:351>


 �[1m11�[0m SKIPPED TESTS
 �[1m1�[0m ERROR
-- Output to stderr:

CMake Error at /home/travis/build/neovim/neovim/cmake/RunTests.cmake:53 (message):
  Running functional tests failed with error: 1.

. Restarting.

ZyX-I · 2017-12-16T14:14:57Z

CI succeeded.

justinmk · 2017-12-16T21:45:39Z

@oni-link done with comments?

oni-link · 2017-12-16T23:18:34Z

@justinmk, I have not yet checked eval.c, otherwise done with .c files.

oni-link · 2017-12-17T08:38:10Z

src/nvim/eval.c

+      TV_LIST_ITER(cur_l, li, {
+        abort = set_ref_in_item(TV_LIST_ITEM_TV(li), copyID, ht_stack,
+                                &list_stack);
+        if (abort) {


The outer enclosing if (!abort) could be removed.

oni-link · 2017-12-17T08:49:53Z

src/nvim/eval.c

+          n = false;
+          break;
+        }
+        case kSpecialVarFalse:


Do we need a a "fallthrough" comment?

Where and why? I have all proper breaks everywhere needed here.

oni-link · 2017-12-17T09:03:26Z

src/nvim/eval.c

@@ -8936,7 +8968,7 @@ static void common_function(typval_T *argvars, typval_T *rettv,
          goto theend;
        }
        list = argvars[arg_idx].vval.v_list;
-        if (list == NULL || list->lv_len == 0) {
+        if (list == NULL || tv_list_len(list) == 0) {


list == NULL could be removed.

oni-link · 2017-12-17T09:16:22Z

src/nvim/eval.c

-        ic = tv_get_number_chk(&argvars[3], &error);
-      }
-      if (error) {
+      idx = tv_list_uidx(l, tv_get_number_chk(&argvars[2], &error));


Why not only error check tv_get_number_chk() here and let tv_list_find() handle the normalization and error handling?

And how I am to get the number to return exactly? tv_list_find() does not return one and I was not feeling like refactoring it to have ret_idx argument as it is useful in two places out of 18 tv_list_find is being used.

oni-link · 2017-12-17T09:31:07Z

src/nvim/eval.c

+        assert(item != NULL);
+      }
+      if (argvars[3].v_type != VAR_UNKNOWN) {
+        ic = !!tv_get_number_chk(&argvars[3], &error);
      }


In the old code the following loop would not be entered, if error was set. error should also be set to false before the call to tv_get_number_chk() if it should be evaluated.

oni-link · 2017-12-17T09:41:28Z

src/nvim/eval.c

@@ -12221,11 +12247,11 @@ static void find_some_match(typval_T *argvars, typval_T *rettv, int type)
      goto theend;
    }
    if (l != NULL) {
-      li = tv_list_find(l, start);
+      idx = tv_list_uidx(l, start);
+      li = tv_list_find(l, idx);


Why precompute idx if it is recomputed in this function?

Ah, idx could be used later on. If this is the case computation of idx could be moved after the if block.

oni-link · 2017-12-17T11:48:59Z

src/nvim/eval.c

-          tv_list_item_free(li);
-          l->lv_len--;
+          tv_list_item_remove(l, li);
+          li = tv_list_find(l, idx);


Finding the new li looks kind of expansive. Can't prev_li be reused to set li?

No, it will actually be invalid after removal. Not invalid with the current implementation, but invalid with array-based list implementation that may trigger realloc() at removal. I know that this is suboptimal, but I also know that uniq() is almost never used.

After searching for uniq() calls in the plugins that happened to be in my ~/.vam I found exactly one user of actual uniq() (that is, neosnippet) and a bunch of uniq() implementations based on dictionary (those that do not do sorting), though I do not quite understand WTF author was thinking when writing such code as

function! deoplete#util#uniq(list) abort let list = map(copy(a:list), '[v:val, v:val]') let i = 0 let seen = {} while i < len(list) let key = string(list[i][1]) if has_key(seen, key) call remove(list, i) else let seen[key] = 1 let i += 1 endif endwhile return map(list, 'v:val[0]') endfunction

(it is not only deoplete, same thing is copied over in some other plugins). (Basically, what I do not understand is what the first and last map()s are for, from my POV you can just copy list over and do remove().)

For reference, my ~/.vam contains something like 200 plugins, though most normally not updated as I only installed them to check something.

Oh, I remembered that I actually bothered to clone all repositories from https://github.com/vim-scripts once in Jun 18, may search that for uniq(). The following is all what ag managed to find there:

% ag '^\s*(?!")\S.*(?<![#a-zA-Z0-9.]|\b\w:)\buniq\(' -G '.*\.vim' ../vim-scripts | tee uniqs.lst ../vim-scripts/AmbiCompletion.git/plugin/ambicompletion.vim:151: call uniq(candidates) ../vim-scripts/AmbiCompletion.git/plugin/ambicompletion.vim:316: call uniq(cachewords) ../vim-scripts/AmbiCompletion.git/plugin/ambicompletion.vim:355: call uniq(cachewords) ../vim-scripts/changesPlugin.git/autoload/changes.vim:783: call uniq(b:diffhl[i]) ../vim-scripts/changesPlugin.git/autoload/changes.vim:1283: let lines = uniq(lines) ../vim-scripts/changesPlugin.git/autoload/changes.vim:1347: let g:lines=uniq(g:lines) ../vim-scripts/clickable.vim.git/autoload/vital/_clickable_vim.vim:265: return uniq(a:list) ../vim-scripts/cmake.vim--Alcin.git/autoload/cmake/extension.vim:49: ../vim-scripts/cmake.vim--Alcin.git/autoload/cmake/extension.vim:50: call uniq(l:signatures) ../vim-scripts/cmake.vim--Alcin.git/autoload/cmake/extension/ninja.vim:47: call uniq(l:flags) ../vim-scripts/cmake.vim--Alcin.git/autoload/cmake/extension/ninja.vim:117: call uniq(l:ninja_file_lines) ../vim-scripts/columnmove.git/autoload/vital/_columnmove.vim:265: return uniq(a:list) ../vim-scripts/ctrlp-locate.git/autoload/vital/_ctrlp_locate.vim:276: return uniq(a:list) ../vim-scripts/Dutyl.git/autoload/dutyl/util.vim:81: return uniq(sort(a:list)) ../vim-scripts/incsearch.vim.git/autoload/vital/_incsearch.vim:282: return uniq(a:list) ../vim-scripts/ingo-library.git/autoload/ingo/compat.vim:93: return uniq(a:list) ../vim-scripts/open-browser.vim.git/autoload/vital/_openbrowser.vim:265: return uniq(a:list) ../vim-scripts/projectionist.vim.git/autoload/projectionist.vim:29: return uniq(a:list) ../vim-scripts/tsuquyomi.git/autoload/vital/_tsuquyomi.vim:266: return uniq(a:list) ../vim-scripts/unite-spell-suggest.git/autoload/mklib/string.vim:142: return a:0 && a:1 ? uniq(sort(l:parts)) : l:parts ../vim-scripts/vim-gista.git/autoload/vital/_vim_gista.vim:247: return uniq(a:list) ../vim-scripts/vim-javacomplete2.git/autoload/javacomplete/server.vim:15: return uniq(a:list) ../vim-scripts/vim-operator-flashy.git/autoload/vital/_operator_flashy.vim:272: return uniq(a:list) ../vim-scripts/vim-pandoc-bundle.git/autoload/pandoc/command.vim:72: return filter(uniq(extend(sort(short_opts), sort(long_opts))), 'v:val != "-:"') ../vim-scripts/vim-signjk-motion.git/autoload/vital/_signjk.vim:272: return uniq(a:list) ../vim-scripts/vim-snoopy.git/autoload/vital/_snoopy.vim:266: return uniq(a:list) ../vim-scripts/vison.git/autoload/vital/_vison.vim:266: return uniq(a:list)

ZyX-I · 2017-12-17T15:12:53Z

CI succeeded.

justinmk · 2017-12-19T10:31:13Z

Conflict in quickfix.c

ZyX-I · 2017-12-23T12:31:37Z

Conflict resolved, though it was almost about nothing: static initializer of the structure I edited was replaced with memset. I thought lists are used more often to cause conflicts with actual list changes.

justinmk · 2017-12-23T15:28:17Z

test/functional/eval/interrupt_spec.lua

+local len = 131072
+
+describe('List support code', function()
+  if not pending('does not actually allows interrupting with just got_int', function() end) then return end


The if not pending check seems like a mistake. Would be clearer:

pending('does not actually allows interrupting with just got_int', function() end) return

Or remove it totally?

I wrote it this way so that it is clear that return is there due to pending and to write everything in one line (one-line if is sometimes used, two syntactically unconnected statements on one line are not).

FEATURES: 3cc7ebf #7234 built-in VimL expression parser 6a7c904 #4419 implement <Cmd> key to invoke command in any mode b836328 #7679 'startup: treat stdin as text instead of commands' 58b210e :digraphs : highlight with hl-SpecialKey #2690 7a13611 #8276 'startup: Let `-s -` read from stdin' 1e71978 events: VimSuspend, VimResume #8280 1e7d5e8 #6272 'stdpath()' f96d99a #8247 server: introduce --listen e8c39f7 #8226 insert-mode: interpret unmapped META as ESC 98e7112 msg: do not scroll entire screen (#8088) f72630b #8055 let negative 'writedelay' show all redraws 5d2dd2e win: has("wsl") on Windows Subsystem for Linux #7330 a4f6cec cmdline: CmdlineEnter and CmdlineLeave autocommands (#7422) 207b7ca #6844 channels: support buffered output and bytes sockets/stdio API: f85cbea #7917 API: buffer updates 418abfc #6743 API: list information about all channels/jobs. 36b2e3f #8375 API: nvim_get_commands 273d2cd #8329 API: Make nvim_set_option() update `:verbose set …` 8d40b36 #8371 API: more reliable/descriptive VimL errors ebb1acb #8353 API: nvim_call_dict_function 9f994bb #8004 API: nvim_list_uis 3405704 #7520 API/UI: forward option updates to UIs 911b1e4 #7821 API: improve nvim_command_output WINDOWS OS: 9cefd83 #8084, #8516 build/win: support MSVC ee4e1fd win: Fix reading content from stdin (#8267) TUI: ffb8904 #8309 TUI: add support for mouse release events in urxvt 8d5a46e #8081 TUI: implement "standout" attribute 6071637 TUI: support TERM=konsole-256color 67848c0 #7653 TUI: report TUI info with -V3 ('verbose' >= 3) 3d0ee17 TUI/rxvt: enable focus-reporting d109f56 #7640 TUI: 'term' option: reflect effective terminal behavior FIXES: ed6a113 #8273 'job-control: avoid kill-timer race' 4e02f1a #8107 'jobs: separate process-group' 451c48a terminal: flush vterm output buffer on pty output #8486 5d6732f :checkhealth fixes #8335 53f11dc #8218 'Fix errors reported by PVS' d05712f inccommand: pause :terminal redraws (#8307) 51af911 inccommand: do not execute trailing commands #8256 84359a4 terminal: resize to the max dimensions (#8249) d49c1dd #8228 Make vim_fgets() return the same values as in Vim 60e96a4 screen: winhl=Normal:Background should not override syntax (#8093) 0c59ac1 #5908 'shada: Also save numbered marks' ba87a2c cscope: ignore EINTR while reading the prompt (#8079) b1412dc #7971 ':terminal Enter/Leave should not increment jumplist' 3a5721e TUI: libtermkey: force CSI driver for mouse input #7948 6ff13d7 #7720 TUI: faster startup 1c6e956 #7862 TUI: fix resize-related segfaults a58c909 #7676 TUI: always hide cursor when flushing, never flush buffers during unibilium output 303e1df #7624 TUI: disable BCE almost always 249bdb0 #7761 mark: Make sure that jumplist item will not have zero lnum 6f41ce0 #7704 macOS: Set $LANG based on the system locale a043899 #7633 'Retry fgets on EINTR' CHANGES: ad60927 #8304 default to 'nofsync' f3f1970 #8035 defaults: 'fillchars' a6052c7 #7984 defaults: sidescroll=1 b69fa86 #7888 defaults: enable cscopeverbose 7c4bb23 defaults: do :filetype stuff unless explicitly "off" 2aa308c #5658 'Apply :lmap in macros' 8ce6393 terminal: Leave 'relativenumber' alone (#8360) e46534b #4486 refactor: Remove maxmem, maxmemtot options 131aad9 win: defaults: 'shellcmdflag', 'shellxquote' #7343 c57d315 #8031 jobwait(): return -2 on interrupt also with timeout 6452831 clipboard: macOS: fallback to tmux if pbcopy is broken #7940 300d365 #7919 Make 'langnoremap' apply directly after a map ada1956 #7880 'lua/executor: Remove lightuserdata' INTERNAL: de0a954 #7806 internal statistics for list impl dee78a4 #7708 rewrite internal list impl

ZyX-I added 2 commits December 10, 2017 03:40

eval/typval: Add functions useful for hiding list implementation

ddce5bc

eval/typval: Add macros useful for hiding list item implementation

49dd615

ZyX-I mentioned this pull request Dec 10, 2017

Fix edge cases for NULL typval_T Lists #4615

Closed

30 tasks

ZyX-I added 3 commits December 10, 2017 04:00

*: Start hiding list implementation

274f32d

Most of files, except for eval.c and eval/* were only processed by perl.

eval: Fix inputlist()

21745d7

eval: Fix writefile()

5c1ddb5

ZyX-I force-pushed the hide-container-impl branch from af4a324 to 5c1ddb5 Compare December 10, 2017 01:01

marvim added the WIP label Dec 10, 2017

ZyX-I added 12 commits December 10, 2017 22:04

*: Hide list implementation in other files as well

ac4bbf5

eval,functests: Fix tests and complete() and setline() behaviour

f572bd7

eval: Fix setmatches(), setqflist() and setloclist()

5008205

quickfix: Fix :cexpr and :lexpr

83f77c8

functests: Mark islocked("v:_null_list") behaviour correct

0b03ac2

It is the same for other VAR_FIXED lists.

eval/encode: Fix crash in json_encode test suite

7572d5a

eval: Fix uniq() crash in legacy test 055

d11884d

functests: Add some more NULL tests

622d355

eval: Still check for NULL when doing :unlet

fe55f37

*: Fix test failures

ceb45a0

*: Finish hiding list implementation

d46e37c

*: Fix linter errors

f4132fb

ZyX-I changed the title ~~[WIP] Hide list implementation~~ [RFC] Hide list implementation Dec 11, 2017

eval: Fix add()

1a961b5

ZyX-I force-pushed the hide-container-impl branch from 9f99e03 to 1a961b5 Compare December 11, 2017 07:35

ZyX-I mentioned this pull request Dec 11, 2017

Viml: null list, add() and setline() #7695

Closed

oni-link reviewed Dec 11, 2017

View reviewed changes

marvim added RFC and removed WIP labels Dec 11, 2017

eval/typval: Fix typo

9f53442

[ci skip]

ZyX-I force-pushed the hide-container-impl branch from 5d89560 to 91d3efa Compare December 15, 2017 22:49

ZyX-I added 2 commits December 16, 2017 14:21

eval: Fix linter error

76ffe0c

Merge branch 'master' into hide-container-impl

7f3b9a4

functests: Fix linter error

0236314

oni-link reviewed Dec 17, 2017

View reviewed changes

eval: Fix some issues found in review

edccf18

Merge branch 'master' into hide-container-impl

c9ab209

ZyX-I added 2 commits December 23, 2017 15:47

regexp: Fix linter errors

d2c01d5

clint: Make linter report line where it found opening brace

5cb7a70

justinmk reviewed Dec 23, 2017

View reviewed changes

justinmk merged commit dee78a4 into neovim:master Dec 23, 2017

justinmk removed the RFC label Dec 23, 2017

ZyX-I deleted the hide-container-impl branch December 23, 2017 18:24

ZyX-I mentioned this pull request Dec 23, 2017

[RFC] Remove some tv_list_item_…() functions #7762

Merged

Uh oh!

[RFC] Hide list implementation #7708

[RFC] Hide list implementation #7708

Uh oh!

Conversation

ZyX-I commented Dec 10, 2017

Uh oh!

ZyX-I commented Dec 11, 2017

Uh oh!

justinmk commented Dec 11, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ZyX-I commented Dec 16, 2017

Uh oh!

ZyX-I commented Dec 16, 2017

Uh oh!

ZyX-I commented Dec 16, 2017

Uh oh!

ZyX-I commented Dec 16, 2017

Uh oh!

justinmk commented Dec 16, 2017

Uh oh!

oni-link commented Dec 16, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ZyX-I Dec 17, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ZyX-I commented Dec 17, 2017

Uh oh!

justinmk commented Dec 19, 2017

Uh oh!

ZyX-I commented Dec 23, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ZyX-I Dec 17, 2017 •

edited

Loading