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";
}
}