Neovim Adopts New Powerful Glob Implementation

3 days ago 2

The original test result for correctness of current vim.glob.to_lpeg could be an reason for migrating to new implementation:

$ luajit testvimglob.lua Assertion failed for pattern '*' matching '': expected true, got nil Assertion failed for pattern 'a*' matching 'a': expected true, got nil Assertion failed for pattern '*a' matching 'a': expected true, got nil Assertion failed for pattern 'a\*b' matching 'a*b': expected true, got nil Assertion failed for pattern '[abc]' matching 'a': expected true, got nil Assertion failed for pattern '[abc]' matching 'b': expected true, got nil Assertion failed for pattern '[abc]' matching 'c': expected true, got nil Assertion failed for pattern 'x[abc]x' matching 'xax': expected true, got nil Assertion failed for pattern 'x[abc]x' matching 'xbx': expected true, got nil Assertion failed for pattern 'x[abc]x' matching 'xcx': expected true, got nil Assertion failed for pattern '[?]' matching '?': expected true, got nil Assertion failed for pattern '[*]' matching '*': expected true, got nil Assertion failed for pattern '[a-cx]' matching 'a': expected true, got nil Assertion failed for pattern '[a-cx]' matching 'b': expected true, got nil Assertion failed for pattern '[a-cx]' matching 'c': expected true, got nil Assertion failed for pattern '[a-cx]' matching 'x': expected true, got nil Assertion failed for pattern '[!abc]' matching 'd': expected true, got nil Assertion failed for pattern '[\!]' matching '!': expected true, got nil Basic pattern tests complete Test Summary: 35/53 tests passed Accuracy: 66.04% Precision: 48.57% Assertion failed for pattern '*' matching '': expected true, got nil Assertion failed for pattern '*.ts' matching '.ts': expected true, got nil Assertion failed for pattern 'a*b*c*d*e*' matching 'axbxcxdxe': expected true, got nil Assertion failed for pattern 'a*b*[cy]*d*e*' matching 'axbxcxdxexxx': expected true, got nil Assertion failed for pattern 'a*b*[cy]*d*e*' matching 'axbxyxdxexxx': expected true, got nil Assertion failed for pattern 'a*b*[cy]*d*e*' matching 'axbxxxyxdxexxx': expected true, got nil Assertion failed for pattern 'z*.js' matching 'z.js': expected true, got nil Assertion failed for pattern '*/z*.js' matching 'a/z.js': expected true, got nil Assertion failed for pattern 'a/z*.js' matching 'a/z.js': expected true, got nil Assertion failed for pattern '*/*' matching '/ab': expected true, got nil Assertion failed for pattern '*/*z*/*/*i' matching 'ab/zzz/ejkl/hi': expected true, got nil Assertion failed for pattern 'a*.txt' matching 'a.txt': expected true, got nil Assertion failed for pattern 'a/**/b' matching 'a/a/bb': expected false, got 7 Assertion failed for pattern 'a/**/b' matching 'a/bb': expected false, got 5 Assertion failed for pattern '**/' matching 'foo/bar': expected false, got 8 Assertion failed for pattern '**/' matching 'a/a': expected false, got 4 Assertion failed for pattern '**/' matching 'a/a': expected false, got 4 Star tests complete Test Summary: 202/219 tests passed Accuracy: 92.24% Precision: 89.29% Assertion failed for pattern 'a/**/b' matching 'a/bb': expected false, got 5 Assertion failed for pattern 'a/**/' matching 'a/b': expected false, got 4 Assertion failed for pattern 'a/**/' matching 'a/b/c/d': expected false, got 8 Assertion failed for pattern 'a/**/' matching 'a/bb': expected false, got 5 Assertion failed for pattern 'a/**/' matching 'a/cb': expected false, got 5 Assertion failed for pattern '**/' matching 'a': expected false, got 2 Assertion failed for pattern '**/' matching 'a/b': expected false, got 4 Assertion failed for pattern '**/' matching 'a/b/c': expected false, got 6 Assertion failed for pattern '**/' matching 'a/b/c/d': expected false, got 8 Globstar tests complete Test Summary: 186/195 tests passed Accuracy: 95.38% Precision: 100.00% Assertion failed for pattern 'foo[{a,b}]baz' matching 'foo{baz': expected true, got nil Assertion failed for pattern 'a{a,b/}*.txt' matching 'aa.txt': expected true, got nil Assertion failed for pattern 'a{a,b/}*.txt' matching 'ab/.txt': expected true, got nil Assertion failed for pattern 'a{,/}*.txt' matching 'a.txt': expected true, got nil Assertion failed for pattern 'a{,.*{foo,db},\(bar\)}.txt' matching 'a.txt': expected true, got nil Assertion failed for pattern 'a{,.*{foo,db},\(bar\)}.txt' matching 'a.db.txt': expected true, got nil Assertion failed for pattern 'a{,*.{foo,db},\(bar\)}.txt' matching 'a.txt': expected true, got nil Assertion failed for pattern 'a{,*.{foo,db},\(bar\)}.txt' matching 'a.db.txt': expected true, got nil Assertion failed for pattern 'a{,.*{foo,db},\(bar\)}' matching 'a.db': expected true, got nil Assertion failed for pattern 'a{,*.{foo,db},\(bar\)}' matching 'a.db': expected true, got nil Assertion failed for pattern '{,.*{foo,db},\(bar\)}' matching '.db': expected true, got nil Assertion failed for pattern '{*,*.{foo,db},\(bar\)}' matching 'a': expected true, got nil Assertion failed for pattern '{,*.{foo,db},\(bar\)}' matching 'a.db': expected true, got nil Assertion failed for pattern '*{*a,b}' matching 'xba': expected true, got nil Assertion failed for pattern 'test.{j*g,p*g}' matching 'test.jpg': expected true, got nil Assertion failed for pattern 'test.{j*g,p*g}' matching 'test.jpxxxg': expected true, got nil Assertion failed for pattern 'test.{j*g,p*g}' matching 'test.jxg': expected true, got nil Assertion failed for pattern 'test.{j*g,j*c}' matching 'test.jnc': expected true, got nil Assertion failed for pattern 'test.{jpg,p*g}' matching 'test.png': expected true, got nil Assertion failed for pattern 'test.{jpg,p*g}' matching 'test.pxg': expected true, got nil Assertion failed for pattern 'test.{jp\,g,png}' matching 'test.jp,g': expected true, got nil Assertion failed for pattern 'test/{foo*,bar*}/baz' matching 'test/foooooo/baz': expected true, got nil Assertion failed for pattern 'test/{foo*,bar*}/baz' matching 'test/barrrrr/baz': expected true, got nil Assertion failed for pattern 'test/{*foo,*bar}/baz' matching 'test/xxxxfoo/baz': expected true, got nil Assertion failed for pattern 'test/{*foo,*bar}/baz' matching 'test/xxxxbar/baz': expected true, got nil Assertion failed for pattern 'a/{a{a,b},b}' matching 'a/aa': expected true, got nil Assertion failed for pattern 'a/{a{a,b},b}' matching 'a/ab': expected true, got nil Assertion failed for pattern 'a/{a{a,b},b}' matching 'a/b': expected true, got nil Assertion failed for pattern 'a/{b,c[}]*}' matching 'a/b': expected true, got nil Assertion failed for pattern 'a/{b,c[}]*}' matching 'a/c}xx': expected true, got nil Brace expansion tests complete Test Summary: 71/101 tests passed Accuracy: 70.30% Precision: 58.33% Assertion failed for pattern 'F[ë£a]' matching '': expected true, got nil Assertion failed for pattern 'F[ë£a]' matching '': expected true, got nil Assertion failed for pattern 'F[ë£a]' matching 'Fa': expected true, got nil Unicode pattern tests complete Test Summary: 8/11 tests passed Accuracy: 72.73% Precision: 70.00% Assertion failed for pattern '**-**.**-**' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**-b**c-**' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**-b.c-**' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**.**-**' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**.**-d' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**.c-**' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern 'a-**.**-d' matching 'a-b.c-d': expected true, got nil Assertion failed for pattern '**.**' matching 'a.b': expected true, got nil Assertion failed for pattern '**.b' matching 'a.b': expected true, got nil Assertion failed for pattern 'a.**' matching 'a.b': expected true, got nil Assertion failed for pattern 'a/**b' matching 'a/b': expected true, got nil Assertion failed for pattern 'a/**b**/c' matching 'a/aba/c': expected true, got nil Assertion failed for pattern 'a/**b**/c' matching 'a/b/c': expected true, got nil Assertion failed for pattern 'a/b/c**/*.js' matching 'a/b/c/d.js': expected true, got nil Extension tests complete Test Summary: 10/24 tests passed Accuracy: 41.67% Precision: 17.65%

And here's my Peglob's result:

$ luajit testpeglob.lua Basic pattern tests complete Test Summary: 53/53 tests passed Accuracy: 100.00% Precision: 100.00% Star tests complete Test Summary: 219/219 tests passed Accuracy: 100.00% Precision: 100.00% Assertion failed for pattern 'a/**/*' matching 'a/': expected false, got 3 Assertion failed for pattern 'a/**/**/*' matching 'a/': expected false, got 3 Assertion failed for pattern 'a/**/**/**/*' matching 'a/': expected false, got 3 Globstar tests complete Test Summary: 192/195 tests passed Accuracy: 98.46% Precision: 100.00% Invalid grammar for pattern 'a/{b,c[}]*}' matching 'a/b' Invalid grammar for pattern 'a/{b,c[}]*}' matching 'a/c}xx' Brace expansion tests complete Test Summary: 99/101 tests passed Accuracy: 98.02% Precision: 97.22% Unicode pattern tests complete Test Summary: 11/11 tests passed Accuracy: 100.00% Precision: 100.00% Invalid grammar for pattern '**-bc-**' matching 'a-b.c-d' Invalid grammar for pattern '**-**.**-**' matching 'a-b.c-d' Invalid grammar for pattern '**-b**c-**' matching 'a-b.c-d' Invalid grammar for pattern '**-b.c-**' matching 'a-b.c-d' Invalid grammar for pattern '**.**' matching 'a-b.c-d' Invalid grammar for pattern '**.**-**' matching 'a-b.c-d' Invalid grammar for pattern '**.**-d' matching 'a-b.c-d' Invalid grammar for pattern '**.c-**' matching 'a-b.c-d' Invalid grammar for pattern '**b.**d' matching 'a-b.c-d' Invalid grammar for pattern 'a**.c**' matching 'a-b.c-d' Invalid grammar for pattern 'a-**.**-d' matching 'a-b.c-d' Invalid grammar for pattern '**.**' matching 'a.b' Invalid grammar for pattern '**.b' matching 'a.b' Invalid grammar for pattern 'a.**' matching 'a.b' Invalid grammar for pattern '**c' matching 'a/b/c' Invalid grammar for pattern 'a/**b' matching 'a/b' Invalid grammar for pattern 'a/**c' matching 'a/b/c' Invalid grammar for pattern 'a/**z' matching 'a/b/c' Invalid grammar for pattern 'a/**b**/c' matching 'a/b/c/b/c' Invalid grammar for pattern 'a/**b**/c' matching 'a/aba/c' Invalid grammar for pattern 'a/**b**/c' matching 'a/b/c' Invalid grammar for pattern 'a/b/c**/*.js' matching 'a/b/c/d.js' Invalid grammar for pattern 'a/b/c**/*.js' matching 'a/b/c/d/e.js' Invalid grammar for pattern 'foo**bar' matching 'foo/baz/bar' Extension tests complete Test Summary: 0/24 tests passed Accuracy: 0.00% Precision: 0.00%

And the performance could be boosted a lot for complex patterns. (The data isn't covered in the paper because less than half the tests match as expected)

Peglob {src,extensions}/**/test/**/{fixtures,browser,common}/**/*.{ts,js} time: 2.68 ms {extensions,src}/**/{media,images,icons}/**/*.{svg,png,gif,jpg} time: 2.36 ms {.github,build,test}/**/{workflows,azure-pipelines,integration,smoke}/**/*.{yml,yaml,json} time: 1.00 ms src/vs/{base,editor,platform,workbench}/test/{browser,common,node}/**/[a-z]*[tT]est.ts time: 1.27 ms src/vs/workbench/{contrib,services}/**/*{Editor,Workspace,Terminal}*.ts time: 2.89 ms {extensions,src}/**/{markdown,json,javascript,typescript}/**/*.{ts,json} time: 2.70 ms **/{electron-sandbox,electron-main,browser,node}/**/{*[sS]ervice*,*[cC]ontroller*}.ts time: 4.86 ms {src,extensions}/**/{common,browser,electron-sandbox}/**/*{[cC]ontribution,[sS]ervice}.ts time: 4.31 ms src/vs/{base,platform,workbench}/**/{test,browser}/**/*{[mM]odel,[cC]ontroller}*.ts time: 3.08 ms extensions/**/{browser,common,node}/{**/*[sS]ervice*,**/*[pP]rovider*}.ts time: 1.53 ms --- NeoVim Glob {src,extensions}/**/test/**/{fixtures,browser,common}/**/*.{ts,js} (743 matched), expected 726 {extensions,src}/**/{media,images,icons}/**/*.{svg,png,gif,jpg} time: 4.30 ms {.github,build,test}/**/{workflows,azure-pipelines,integration,smoke}/**/*.{yml,yaml,json} time: 1.29 ms src/vs/{base,editor,platform,workbench}/test/{browser,common,node}/**/[a-z]*[tT]est.ts (0 matched), expected 224 src/vs/workbench/{contrib,services}/**/*{Editor,Workspace,Terminal}*.ts (126 matched), expected 155 {extensions,src}/**/{markdown,json,javascript,typescript}/**/*.{ts,json} time: 4.08 ms **/{electron-sandbox,electron-main,browser,node}/**/{*[sS]ervice*,*[cC]ontroller*}.ts (0 matched), expected 419 {src,extensions}/**/{common,browser,electron-sandbox}/**/*{[cC]ontribution,[sS]ervice}.ts (0 matched), expected 586 src/vs/{base,platform,workbench}/**/{test,browser}/**/*{[mM]odel,[cC]ontroller}*.ts (0 matched), expected 95 extensions/**/{browser,common,node}/{**/*Service*,**/*Provider*}.ts (0 matched), expected 3
Read Entire Article