Fixing Native Stack Depth Error in Hyperformula Integration with React Native and HermesJS

[alvarovillafane]

Hi,

I'm currently working on implementing Hyperformula in React Native with the HermesJS engine.
Overall, it works ok, but I'm encountering an error with some formulas. I would greatly appreciate it if you could assist me or provide any ideas/suggestions for a workaround or fix for this issue.

In React Native, many of the standard JavaScript functions such as map, apply, call, and others are converted into native calls. With HermesJS, there is a limitation on the number of native stack calls that can be made at any given time, and this limit is relatively low (128) compared to engines like Chrome V8.

The problem arises when attempting to parse a formula in Hyperformula using either the calculatingFormulas or setSheetContent functions, and the formula contains more than two levels of nested parentheses.
For example, formulas like =(((8))) or =(A1*B2+((C2/10)/10)/10) would result in a RangeError: Maximum call stack size exceeded (native stack depth).

This issue occurs because Chevrotain parsing relies on recursive functions that use apply and call multiple times, leading to the exceeding of the native stack depth.

You can see the code here:
https://github.com/Chevrotain/chevrotain/blob/d8593c78e919f8f03fce04c2c4860a3022af7e4f/packages/chevrotain/src/parse/parser/traits/recognizer_engine.ts#L245

and

https://github.com/Chevrotain/chevrotain/blob/d8593c78e919f8f03fce04c2c4860a3022af7e4f/packages/chevrotain/src/parse/parser/traits/recognizer_engine.ts#LL225C23-L225C23

There is a way to avoid Chevrotain doing this many recursive iterations, or to parse the formula in a different way so I can avoid hitting the limits?

Here is a repo with an example on when it fails:
https://github.com/vmalvaro/hermes-range-error

This is some HermesJS similar issues for more context:

facebook/hermes#135 (comment)

facebook/hermes#135 (comment)

Thanks for your help!!

[AMBudnik]

That's an interesting case there, @vmalvaro

The first question that arises is why the limit is so low? It seems to be blocking developers in many different occasions cause if not HyperFormula they may be blocked somewhere else. The best idea would be to raise the limit or let developers decide how deep they want to go.

Nevertheless, I think that we'd need to get @sequba 's feedback here. At the first glance, I do not see an easy way to exclude Chevrotain from the equation.

Would it be an issue to get back to you within ~3weeks?

[alvarovillafane]

Thanks for your quick response @AMBudnik, yes, am not sure why it's so low and it's a bit of a pain 😞

I've brought up the issue with Meta's dev team (see facebook/hermes#135 (comment)). They have suggested building a custom engine with a higher value, but it appears to be a complex task to integrate it with React Native and keep it up to date.

While it might be challenging to bypass Chevrotain, I wonder if there are any alternative solutions or workarounds. Perhaps updating Chevrotain to the latest version could help, although I'm not entirely convinced.

Another issue we are facing is the overuse of call/apply in Chevrotain, which exacerbates the problem of the low limit of native calls.

Currently, we have had to limit the depth of nested parentheses to only 2 to avoid hitting the hard limit of 128. The only solution I have found so far is to monkey patch Chevrotain and reduce the usage of the call/apply function. This has allowed me to increase the limit to 8 nested parentheses, but I am still in the testing phase.

I attempted to examine Chevrotain more closely, and it seems that the main issue lies within their recognize_engine.js file, specifically when calling defineRule. I believe this is related to Hyperformula's usage of Rule/SubRule options, although I'm not entirely sure.

[bd82]

Hello @vmalvaro

There is a way to avoid Chevrotain doing this many recursive iterations, or to parse the formula in a different way so I can avoid hitting the limits?

Chevrotain

I'm not sure if Chevrotain can (or should) be changed for this edge case.
Although I am interested in what kind of monkey patching was performed to partially mitigate the issue?

In regards to the grammar:

• hyperformula/src/parser/FormulaParser.ts

  Lines 105 to 122 in b8517a7

  	/**
  	* LL(k) formula parser described using Chevrotain DSL
  	*
  	* It is equivalent to the grammar below:
  	*
  	* F -> '=' E <br/>
  	* B -> K < B | K >= B ... | K <br/>
  	* K -> E & K | E <br/>
  	* E -> M + E | M - E | M <br/>
  	* M -> W * M | W / M | W <br/>
  	* W -> C * W | C <br/>
  	* C -> N | R | O | A | P | num <br/>
  	* N -> '(' E ')' <br/>
  	* R -> A:OFFSET(..) | A:A <br/>
  	* O -> OFFSET(..) | OFFSET(..):A | OFFSET(..):OFFSET(..) <br/>
  	* A -> A1 | $A1 | A$1 | $A$1 <br/>
  	* P -> SUM(..) <br/>
  	*/

It seems to be highly recursive as it seems to use rules hierarchy to define operator precedence.
This is a common practice in parsing expression grammars, but it is also not the most efficient approach...

It may be possible to re-factor the grammar to parse the binary expressions as a flat list
and perform a post-parsing step to apply the correct precedence level.

• e.g. the swift compiler does this:
  • https://docs.swift.org/swift-book/documentation/the-swift-programming-language/expressions/

  • Note At parse time, an expression made up of infix operators is represented as a flat list. This list is transformed into a tree by applying operator precedence. For example, the expression 2 + 3 * 5 is initially understood as a flat list of five items, 2, +, 3, *, and 5. This process transforms it into the tree (2 + (3 * 5)).

However, such a re-factor may be a large undertaking, particularly considering that the grammar is using embedded actions and is not a "pure" grammar. Another benefit would likely be a large performance boost, but I do not know if hyperFormula needs better performance as the use case seems to be about very small inputs.

[alvarovillafane]

thanks @bd82, It just doesn't work in React Native with HermesJS.
Not sure if it's an edge case, is more like it won't work with React Native.

I'm not too familiar with grammar and parsing, but I understand that would be a big change to move away from chevrotain.

I didn't monkey patch yet, I did some tests and POC on how to improve it.
The main issue is with the use (overuse) of apply and call usage on Chevrotain, which are converted to native calls by Hermes JS triggering the error of too many native calls

The solution is to patch the library by removing apply and call when possible, and just to call the function directly.

Just to illustrate an example:

instead of calling fakeFunction.apply(this, params) or fakeFunction.call(this, params) just use direct this.fakeFunction(params) when possible.
On my tests, seemed to work well or at least increase the amount of nested parenthesis by a good margin.