VS Code freeze on specific line

[alexr00]

Originally from microsoft/vscode#92369
Checklist

• This problem exists even with the setting "C_Cpp.enhancedColorization": "Disabled"
• This bug exists for C
• This bug exists for C++
• This bug exists for Objective-C
• This bug exists for Objective-C++

VS Code version 1.43.

The code with a problem is:

std::tuple_element<0, std::pair<pugi::xml_node, std::map<std::basic_string<char>, pugi::xml_node, std::less<std::basic_string<char> >, std::allocator<std::pair<const std::basic_string<char>, pugi::xml_node> > > > >::type dnode

[Yanpas]

One more example (harder one):

 std::_Rb_tree_iterator<std::pair<const long, std::pair<pugi::xml_node, std::map<std::basic_string<char>, pugi::xml_node, std::less<std::basic_string<char> >, std::allocator<std::pair<const std::basic_string<char>, pugi::xml_node> > > > > > dnode_it = dnodes_.find(uid.position)

[matter123]

Performance for the first example

Details

total time: 315883.535238ms

match failure
pattern name             average time    total time   peak time
source.cpp:4818        77339.166134   309356.665   309356.659
source.cpp:3565          658.119408     2632.478     2632.476
source.cpp:1971          656.497709     2625.991     2625.989
source.cpp:7909            0.018155        6.518        0.251
source.cpp:2348            0.014084        0.056        0.051
...

matched, not chosen
pattern name             average time    total time   peak time
source.cpp:14180           4.965007      198.600      150.862
source.cpp:14610           2.178239      270.102      221.351
source.cpp:7951            0.054199        0.054        0.054
source.cpp:16302           0.017617        1.850        0.048
...

matched, chosen
pattern name             average time    total time   peak time
source.cpp:14180         146.496801      292.994      292.953
source.cpp:13621           0.648560       44.751       30.916
source.cpp:14610           0.019626        1.354        0.070
source.cpp:8175            0.016105        0.016        0.016
...

function_definition(4818) is the freeze causing regex, but destructor_root (3565), constructor_root (1971), and scope_resolution_namespace_block_inner_generated (14180) all have unacceptable performance.

[matter123]

@jeff-hykin the pattern seems to spend a lot of time in the recursive template matching, if that could be made more atomic, that would help.

Additionally, it may be a bit of a hack but it might be possible to add a wrapper that looks ahead for ( before attempting to do the expensive function matching.

Something like:

start_pattern: lookAheadFor(/[^(]+/.then(/(/),
end_pattern: lookAheadFor(/./.or(@end_of_line)
includes: [:function_definition],

Edit: the wrapper won't work, if a line contains ( but not a function definition, the grammar will end up in an endless loop, as the wrapper will still match

[jeff-hykin]

Thanks for posting this, sorry I've been gone for awhile. This looks like it is going to be a really tough fix.

First its hard because there's the possibility of comparison vs templating ex:std::tuple_element<0 could be a less than. So there is a decent bit of computation being done for checking that possibility, and that possibility is recursively exploding with each nested template. On top of that function_definition is already a giant/slow pattern because it is trying to match any possible type at the beginning, and it is unclear whether or not that code is a type without parsing nearly the entire thing, and sometimes, as in Yanpas's case, it ends up failing and not even being a type.

Hopefully there's some major inefficiency we can fix, but I imagine were going to have to make some major assumptions, or straight up limit the length of a valid type in order to get rid of this freezing.

[Yanpas]

Nothing will do better highlighting than clang (semantic highlighting). I think that highlighter's performance is more important than accuracy, so I guess incorrect highlighting is better than slow (but not in case like #428 :) ). I saw in a dev tools a lot of heavy regular expressions are executed each time I type some letter.

[jeff-hykin]

I saw in a dev tools a lot of heavy regular expressions are executed each time I type some letter.

Yeah @Yanpas it wouldn't be surprising to me if this repo had the largest/heaviest regex on github, I can't think of any other situation where such a big pattern would be needed

[jeff-hykin]

I found an inefficiency with the <> pattern and fixed it with v1.14.27. I'm going to close this issue since no longer freezes 🎊 , it is still a bit slow but I doubt there is going to be another major performance improvement.

@matter123 the template_call had a maybe(@spaces) after it that was causing the catastrophic backtracking, which was being used in qualified type, which was being used in function definition. I also improved the scope resolution method for qualified type which I believe also helped performance.

[alexr00]

Pulled in the latest changes. Thank you for the fix!

[alexr00]

It looks like for the line in the original issue this is fixed 🎉
But for the line here, I'm still getting a freeze.

[sean-mcmanus]

I hit a repro (VS Code UI freeze) with the following (test) code:

#include <unordered_map>
#include <map>
 
std::unordered_map<
std::string, std::pair<std::string, std::map<std::string, std::map<std::string, std::map<std::string, std::pair<std::string, std::map<std::string, std::map<std::string, std::map<std::string, std::vector<std::string>>>>>>>>>
>
d;

Let me know if I should file a different issue.

[jeff-hykin]

I think this is the right issue, thanks for the additional example

[jeff-hykin]

Looking at this again, while the other example is likely just going to be difficult, your example @sean-mcmanus should be solvable. It still might be awhile before its addressed, and so that this issue doesn't slow everything down a workaround/shutoff for large numbers of <>'s might be introduced to prevent freezing.

[alexr00]

@jeff-hykin any update on a change to prevent freezing? It's been a while since pulled in updates because of this and I want to get all the other good fixes!

[jeff-hykin]

Thanks for pulling this up again, I think the fix for the issue you posted was actually the cause of this freezing. Next time I work at the syntax, I'll try building a workaround for this.

[jeff-hykin]

@alexr00 I do have a question though, did the original example have a semicolon at the end? or was it the beginning type of a function definition?

[alexr00]

The original example did not have a semicolon at the end. It could have been the beginning type of a function definition since that line was coming from the language server, which was likely because that line was needed for a hover somewhere.

[alexr00]

With the latest grammar, I actually don't see a freeze on any of the three examples that used to freeze:

std::tuple_element<0, std::pair<pugi::xml_node, std::map<std::basic_string<char>, pugi::xml_node, std::less<std::basic_string<char> >, std::allocator<std::pair<const std::basic_string<char>, pugi::xml_node> > > > >::type dnode

 std::_Rb_tree_iterator<std::pair<const long, std::pair<pugi::xml_node, std::map<std::basic_string<char>, pugi::xml_node, std::less<std::basic_string<char> >, std::allocator<std::pair<const std::basic_string<char>, pugi::xml_node> > > > > > dnode_it = dnodes_.find(uid.position)

#include <unordered_map>
#include <map>
 
std::unordered_map<
std::string, std::pair<std::string, std::map<std::string, std::map<std::string, std::map<std::string, std::pair<std::string, std::map<std::string, std::map<std::string, std::map<std::string, std::vector<std::string>>>>>>>>>
>
d;

[alexr00]

It looks like VS Code doesn't freeze on issues like this now, it just also doesn't color them. I will pull the grammar updates into VS Code again, since we want all the recent fixes.

[jeff-hykin]

Yeah same here with the latest version of the extension. I think that must be an optimization from vscode textmate (which is what I'd have it ideally have it be). It's still slow when editing those lines, but doesn't freeze.

The solution to this issue would have just been a hack (stop parsing if too long) so I'm going to go ahead and close this issue. Efficient correct parsing of those three simply needs a better parsing engine.