PeterVD wrote:
Hi Walaa,
I wasn't referring to the recursive behaviour of the save, but to the actual implementation or programming of this recursive behaviour.
Is it still programmed using a recursive method call (and possibly leading to a StackOverflowException) or using a while-loop?
This post (in a thread about a different topic) describes it: http://www.llblgen.com/tinyforum/GotoMessage.aspx?MessageID=121313&ThreadID=21465.
I was hoping this code would have been refactored at some point (in version 5.0 for instance), because we are running into the StackOverflowException at the moment.
As I said, it's an extreme case we have. But with a refactoring in LLBLGen, this could be avoided. (I know, that's easy to say for me to say )
As described in the link above, we use Depth First Search to determine the topological order in the DAG made up by entity class instances. We in theory could switch to Kahn's (https://en.wikipedia.org/wiki/Topological_sorting) but in practice there would be a problem: we don't store the graph in a Graph structure with vertices and edges, it's an in-memory object model of entity class instances and references, so to make Kahn's algorithm work, we need to traverse the graph of instances handed to the sorter (where the crash happens). So we first build the graph into an adjacency list datastructure but that precisely goes wrong in your case, so it wouldn't help.
So we then have to rewrite the recursive traversals to non-recursive traversals which gives us a problem: we then have to prove our algorithm is correct (we now can rely on Tarjan and others having done that for us in their papers). And I'm not going to do that, simply because on paper the algorithm is quite simple but in practice implementing this without errors isn't. Believe me when I say there are some mega graphs with all the edge cases you can think of being persisted with this, and we had just 1 bug in it in 10 years (which was caused by one such graph with multiple paths between nodes using inheritance, fun! )
So correctness trumps everything in this case, and we'll not sacrifice that here. Of course, there's always the theory of 'use a stack yourself' and that might work, but it's not that simple in practice, considering the sorter uses 2 passes (one to build the adjacency lists, one to sort these).
There's a solution for your edge case however: http://stackoverflow.com/questions/4513438/c-sharp-recursion-depth-how-deep-can-you-go
It means you have to start a thread and give it a stackspace > 1MB (the default .NET one). In general this isn't needed but in your case you need it.