Repository navigation
Stack overflow in bindBinaryExpressionFlow #35633
Description
From telemetry, seems to be new in 3.6 (not sure when it was introduced, but we started collecting data around the 3.6 timeframe). It's a high hitter in VS.
User report: https://developercommunity.visualstudio.com/content/problem/850916/javascript-error-on-intellisense-initation.html
Error processing request. Maximum call stack size exceeded
RangeError: Maximum call stack size exceeded
at Object.getAssignmentDeclarationKind (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:11540:42)
at bindWorker (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30970:42)
at bind (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30867:13)
at visitNode (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17584:24)
at Object.forEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17804:24)
at bindEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29481:16)
at bindBinaryExpressionFlow (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30180:17)
at bindChildrenWorker (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29542:21)
at bindChildren (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29451:17)
at bind (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30878:21)
at visitNode (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17584:24)
at Object.forEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17804:24)
at bindEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29481:16)
at bindBinaryExpressionFlow (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30180:17)
at bindChildrenWorker (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29542:21)
at bindChildren (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29451:17)
at bind (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30878:21)
at visitNode (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17584:24)
at Object.forEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17804:24)
at bindEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29481:16)
at bindBinaryExpressionFlow (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30180:17)
at bindChildrenWorker (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29542:21)
at bindChildren (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:29451:17)
at bind (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:30878:21)
at visitNode (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17584:24)
at Object.forEachChild (C:\Program Files (x86)\Microsoft SDKs\TypeScript\3.7\tsserver.js:17804:24)
....
Activity
minestarks commentedon Dec 13, 2019
Ryan Cavanaugh (@RyanCavanaugh) can we take this into 3.8 beta?
minestarks commentedon Dec 18, 2019
Daniel Rosenwasser (@DanielRosenwasser) Ryan Cavanaugh (@RyanCavanaugh) here's a corresponding VS bug with some more context. Let me know if I can collect any more data on this that may be of use.
RyanCavanaugh commentedon Dec 18, 2019
A repro (perhaps not the only one):
Generate the file
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 39 + 40 + 41 + 42 + 43 + ... + 1499Then run
We should error with "expression is too complex" or similar instead of crashing when the tree is too deep.
minestarks commentedon Dec 20, 2019
Repro file: https://github.com/openlayers/ol2/blob/master/tests/speed/wmscaps.js
Could we do better than binding recursively? It is an obscenely long expression sure, but it doesn't seem so complex that our only option should be to bail.
RyanCavanaugh commentedon Dec 20, 2019
An expression like this is going to be problematic regardless of what we do in binding, because for something like
a() + b() + c() + d() + e() ..., the type of each expression depends on the narrowing effects of the prior call.weswigham commentedon Dec 20, 2019
...I could always rewrite flow control to use a trampoline a la #32611
minestarks commentedon Dec 20, 2019
So ignore me if it doesn't make any sense, since I don't really know how the compiler works: I understand solving this generally may be extremely tricky, but could we special-case literals (string or numeric)? I would imagine almost all manifestations of this problem involve string literals, and not something where the type needs to be inferred. Though this is just a guess, not based on actual data.
Anyway my main concern is the crash so any solution that fixes that would make me happy 🙂
weswigham commentedon Dec 21, 2019
Max call stack size is like... 12k; so assuming a lowball 5 frames/nested node in frame overhead during control flow, we're still limited to around 2.4k levels of nested/dependent nodes before stacking out (given the example at the top, looks like it's actually closer to 1.5k in reality, so our overhead may be a bit more). (The traversal itself is the stack cost.) We could use a trampoline to traverse the deep AST and measure the tree depth in advance and issue an error that somehow blocks checking - but if we're willing to do that, why wouldn't we just use a trampoline to actually check it. Flow control has 1 well-known entrypoint -
getFlowTypeOfReference. Within that, makinggetTypeAtFlowNodeinto a trampoline should be fairly straightforward, without affecting much other code. The only potential issue is that flow control is super performance sensitive; but it shouldn't be that bad, assuming we don't actually use downleveled generators and use a pool of preallocated step objects where possible.