This patch adds postorder traversal support to the RecursiveASTVisitor.
This feature needs to be explicitly enabled by overriding shouldTraversePostOrder()
as it has performance drawbacks for the iterative Stmt-traversal.
The motivation for this patch is a hashing algorithm for all AST nodes
which reuses child hash values to be O(n) and therefore needs postorder support
(think Java's Object.hashCode() but on AST nodes as an example).
The full code that currently uses this feature can be seen here:
Having postorder traversal makes sense to me. The thing I'm worried about is how much this will bloat object code. RecursiveASTVisitor is already a major contributor to the size of clang's binary and we've hit issues with it in the past (hitting .obj size limits on Windows for example) can you show numbers of the size of clang before and after this change? Ideally in Release and Debug configurations.
If it grows it too much we'll have to find another way of enabling/disabling it.
The previous stats were wrong (only applied this patch, not the patch using the code):
63311672 Byte -> 77212960 Byte (+22% or +13.8 MB)
1240292520 Byte -> 1264866776 Byte (+2% or +24.6 MB)
Agreed. The new patch is now reusing the Visit methods so that the executable size stays the same.
The downside is that you can no longer create a single Visitor class that is both post- and preorder traversing,
but I don't think there is any major use case for that.
Does this really give a postorder traversal rather than some kind of postorder / reverse preorder hybrid (based on whether we use data recursion or regular recursion for different parts of the graph)?
I would expect the right way to handle this would be to call PostVisitStmt from the if (Visited) branch above, where we call dataTraverseStmtPost.