Huge expressions blow the stack during evaluation

[joshdistler]

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]

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]

Ah. Interesting. Is this Radar material?

[davedelong]

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.