search

davedelong / DDMathParser

String → Number
MIT License
856 stars 153 forks source link

Huge expressions blow the stack during evaluation #124

Open joshdistler opened 8 years ago

joshdistler commented 8 years ago

Hi Dave.

During some quick testing on the Swift3 branch noticed that if I do evaluation on an extremely long series of calculations (say simple +-*/ stuff on randomly generated integers where the number of operators might be 1000 or more) I'm seeing crashes in DDMathParser.

The strange thing is that it only appears to happen when running the evaluation on a background thread (either via OperationQueue or DispatchQueue).

Is this expected? Am I using it wrong? Obviously if I break down the long series into an array of short calculations, and handle each item separately, it works fine but seems like I shouldn't need to do this.

davedelong commented 7 years ago

I just reproduced this, and my gut feeling is that this is an issue related to blowing out the execution stack. When I saw this, I was nearly 400 frames deep in execution, and I'm wondering if at that point we exceed the amount of space that Swift runtime allocates for the execution stack.

joshdistler commented 7 years ago

Ah. Interesting. Is this Radar material?

davedelong commented 6 years ago

I just had the thought that you could do this by doing a DFS traversal of the expression tree without recursing. The current implementation of evaluation is essentially recursing through the entire tree, and on a huge tree, that blows the stack.