Non-recursive visitors like MixedModeVisitor and MixedModeVisitor adopt a post-order DFS function ExpandDataflow to implement their VisitExpr method, my question is how does ExpandDataflow support non-recursive visit?
Reading the source code, take CallNode* op for example, ExpandDataflow will push its arguments and its op into a stack, and will process them during the next loops, and if items in the stack are not dataflow nodes, they will be visit by a recursive method fvisit_leaf.
while (stack.size() > 0) {
auto node = stack.top().first;
if (fcheck_visited(node)) {
// if this node was visited through another path
// after being added to the stack ignore it.
stack.pop();
} else if (stack.top().second) {
// all the children have already been expanded.
// we can just run post order visit on it.
fvisit_leaf(node);
stack.pop();
} else if (const CallNode* op = node.as<CallNode>()) {
// mark expanded = true
stack.top().second = true;
// push the children to the stack in reverse order
// to match recursive processing order
for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
fpush_to_stack(*it);
}
fpush_to_stack(op->op);
} else if (const TupleNode* op = node.as<TupleNode>()) {
stack.top().second = true;
// push the children to the stack in reverse order
// to match recursive processing order
for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
fpush_to_stack(*it);
}
} else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
stack.top().second = true;
fpush_to_stack(op->tuple);
} else {
// No need to expand the children directly run visit.
fvisit_leaf(node);
stack.pop();
}
}
This looks similar compared to recursive VisitExpr, take CallNode* op for example, recursive VisitExpr will visit its span, op, type_args, args recursively.
void ExprVisitor::VisitExpr_(const CallNode* op) {
this->VisitSpan(op->span);
this->VisitExpr(op->op);
for (auto ty_arg : op->type_args) {
this->VisitType(ty_arg);
}
for (auto arg : op->args) {
this->VisitExpr(arg);
}
}
This really puzzles me, I did not understand how this post-order DFS visit function helps to avoid the stack size problem of recursive visit. Can anyone show me some ideas? Thanks a lot.