Hello,
As much as I know recursive programming is dangerous and possibly not scalable, I don't have much of a choice here.
To put it simply, I have a tree of elements that represent a hierarchy of components (FlowVR application), and my function, for every node, outputs a subgraph to a Graphviz DOT text file. Every node can contain subgraphs.
Since I have some understanding of how the stack works, most of my variables are dynamically allocated to the heap. As a result I only have pointers and a few strings with tops 50 chars as local variables.
Here's the recursive function's header:
void renderNode(Component* node, ofstream& Fdot, int depth, Viewer* v)
If I get it right, I'm only storing 3 bytes and an int in the callstack for every call.
Here's the code. I am sorry, it is a bit beefy and perhaps "light" isn't deserved ^^.
I have highlighted the recursive call.
The code following the call shouldn't be related to my problem, but I've left it just in case.
Here's the catch: this function stack overflows after only 1 to 3 recursive calls.
And I have no bloody idea as to why.
So my question essentially is...
Where could such a problem come from? What could be causing it that I should investigate?
Thanks a lot for your help,
Xavier
Code:void renderNode(Component* node, ofstream& Fdot, int depth, Viewer* v) { // render a node and call recursively on children /* * Symbols * ------- * ## C ## : Compute * The code following this symbol performs computation. * It could produce a formatted cluster label for instance. * * ## W ## : Write * Following code will write to a target file. */ // Is the component a composite? if (!node->children.empty()) { // {component is a composite} v->displayInfo("Component is a composite"); /* * */ // 1) Begin cluster Fdot << genIndent(depth) << " subgraph cluster_" << sanitize(node->id) << " {\n"; /* * */ // 2) Generate a reasonably sized cluster label // You can only see as far as the parent, provided there is one. // Pick a filling color for the cluster. // Write your results. // ##..C ## string clusterLabel; if (node->parent == NULL || node->parent->parent == NULL) // If we're looking at the root node => get the raw id // If we're looking at a level 1 node, get the raw id too clusterLabel = node->id; else { // There is a parent, and the parent isn't root. // This means we have at least two delimiters in our id. const string id = node->id; // pos is the boundary between our component and it's parent int pos = id.find_last_of('/'); // Get a substring and find out where the second boundary is. // Truncate at second delimiter. string subStr = id.substr(0, pos-1); int pos2 = subStr.find_last_of('/'); clusterLabel = id.substr(pos2 +1); } // {clusterLabel is fit for duty and not sanitized, as it isn't a dot ID} // ## W ## Cluster label and fillcolor v->displayInfo("About to write to file"); Fdot << genIndent(depth+1) << " label=\"" << clusterLabel << "\";\n"; Fdot << genIndent(depth+1) << " fillcolor=\"#" << selectClusterFillColor(depth) << "\";\n"; /* * */ v->displayInfo("About to render children nodes"); // 3) Render children nodes for (std::list<Component*>::iterator c = node->children.begin(); c != node->children.end(); c++) { v->displayInfo("From composite -> renderNode"); // RECURSIVE CALL renderNode((*c), Fdot, depth+1, v); // RECURSIVE CALL } /* * */ // 4) Render ports // ##..W ## Input Fdot << genIndent(depth+1) << " subgraph " << sanitize(node->id) << "_inputPorts_ {\n"; Fdot << genIndent(depth+2) << " label=\"\"\n"; Fdot << genIndent(depth+2) << " rank=same\n"; // Browse through all the ports for (std::list<Port*>::iterator p = node->ports.begin(); p != node->ports.end(); p++) { if ((*p)->type == "INPUT") { // We've found an input port Fdot << genIndent(depth+2) << " " << sanitize(node->id) << " " << (*p)->id << " [ label=\"" << (*p)->id << "\", shape=square, style=filled, fillcolor=" << determinePortColor(*p) << " ];\n"; } }//{input ports rendered} Fdot << genIndent(depth + 1) << " }\n"; // ##..W ##..Output Fdot << genIndent(depth + 1) << " subgraph " << sanitize(node->id) << "_outputPorts_ {\n"; Fdot << genIndent(depth + 2) << " label=\"\"\n"; Fdot << genIndent(depth + 2) << " rank=same\n"; // Browse through all the ports for (std::list<Port*>::iterator p = node->ports.begin(); p != node->ports.end(); p++) { if ((*p)->type == "OUTPUT") { // We've found an output port Fdot << genIndent(depth + 2) << " " << sanitize(node->id) << " " << (*p)->id << " [ label=\"" << (*p)->id << "\", shape=square, style=filled, fillcolor=" << determinePortColor(*p) << " ];\n"; } }//{output ports rendered} Fdot << genIndent(depth + 1) << " }\n"; /* * */ // 5) Links // If you're reaching a primitive's port, the separator you have to use is ':' // On the other hand, if you're reaching a composite's port, the separator is '__' // Be careful, as those are _two_ underscores. // This naming convention for composite ports gets rid of a major conflict and introduces a smaller one instead. // Thanks to this addition, you can have a port "A" and a component "A" living in the same composite. // But you can't have a port "A" and a component "_A" in the same composite, as those will collide. // You can have a port "_A" and a component "A" though. // This should not happen, but you never know. // The easy way to tackle this is to forbid component names to begin with an underscore. // If you are willing to change this naming convention, // be well aware that only alphanumerical characters and underscores are allowed in a DOT ID. // ##..C ##..\AND/ ##..W ## mixed // Process every link for (std::list<LinkBetweenComponents*>::iterator l = node->links.begin(); l != node->links.end(); l++) { // Let's find source if ((*l)->source == node->id) { // source is the working node // ## W ## Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << "__" << (*l)->outport << " ->"; // {we're done with the source} } else { // source is not the working node // Browse through children components to find it for (std::list<Component*>::iterator c = node->children.begin(); c != node->children.end(); c++) { if ((*c)->id == (*l)->source) { // We have found the source node if (!(*c)->children.empty()) { // Source node is a composite // ## W ## Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << "__" << (*l)->outport << " ->"; } else { // Source node is a primitive // ## W ## Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << ":" << (*l)->outport << " ->"; } // {we're done with the source} } } } // {source part of the link written} // Let's find dest if ((*l)->dest == node->id) { // dest is the working node // ## W ## Fdot << sanitize((*l)->dest) << "__" << (*l)->inport << "\n"; // {we're done with the dest} } else { // dest is not the working node // Browse through children components to find it for (std::list<Component*>::iterator c = node->children.begin(); c != node->children.end(); c++) { if ((*c)->id == (*l)->dest) { // We have found the dest node if (!(*c)->children.empty()) { // Dest node is a composite // ## W ## Fdot << sanitize((*l)->dest) << "__" << (*l)->inport << "\n"; } else { // Dest node is a primitive // ## W ## Fdot << sanitize((*l)->dest) << ":" << (*l)->inport << "\n"; } // {we're done with the dest} } } } // {dest part of the link written} // {link written} }// {all links are processed} Fdot << genIndent(depth) << " }\n"; // #end cluster v->displayInfo("End of composite"); }//#endcomposite else if (node->type == "connection") { Fdot << genIndent(depth) << " " << sanitize(node->id) << " [ shape=" << shapeToUse(node->type) << ", label=\"" << generateLabel(node) << "\" ];\n"; } else { // {component is a primitive} Fdot << genIndent(depth) << " " << sanitize(node->id) << " [ shape=" << shapeToUse(node->type) << ", style=" << selectStyle(node) << ", fillcolor=" << selectFillColor(node) << ", label=\"" << generateLabel(node) << "\" ];\n"; } }
Originally Posted by Salem
