[cfe-dev] Why is RecursiveASTVisitor::TraverseStmt structured differently from other Traverse*s?

[Richard Smith via cfe-dev]

On Mon, 6 Jan 2020 at 17:35, David Rector via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> I have been experimenting with adjusting RecursiveASTVisitor to perform
> VisitPre* and VisitPost* (via corresponding WalkUpFromPre* and
> WalkUpFromPost* methods) surrounding the inner component traversals within
> each Traverse* definition.  This would allow one to easily define visitors
> that can e.g. keep track of the current traversal state, do pushes/pops
> around traversals of selected node kinds, etc.
>

Can you say more about what you want to do here? The kinds of things I
think you're describing can already be done straightforwardly by overriding
the Traverse* methods, and we have several visitors in Clang that do that
kind of thing, so either I'm not understanding or there may already be a
good way to do what you're trying to do. (For example, at the top of
lib/Sema/SemaTemplateVariadic.cpp,
the CollectUnexpandedParameterPacksVisitor keeps track of and pushes/pops
traversal state while it's traversing a LambdaExpr.)


> This works great with Decl and Type nodes, as DEF_TRAVERSE_DECL and
> DEF_TRAVERSE_TYPE are straightforward: if a node D has children D1 and D2,
> which in turn have children d11 and d12 / d21 and d22 respectively, the
> descendants of D will be processed in this order:
>
> D1, d11, d12, D2, d21, d22
>
> So, my VisitPre*Decl(D1) and VisitPost*Decl(D1) would surround all the
> visitations of d11 and d12 and their descendants and none of D2’s
> visitations, as one might expect.
>
> However, DEF_TRAVERSE_STMT is another matter entirely.  It endows each
> Traverse* function with a "DataRecursionQueue *" parameter.  No specific
> traversals definitions seem to use it idiosyncratically though — instead,
> all that parameter seems to do is permit the root TraverseStmt definition
> to process descendants of a Stmt S in the following order, if I am not
> mistaken:
>
> S1, S2, s11, s12, s21, s22
>
> This defeats my intention of fully surrounding the processing of e.g. S1
> and its descendants with pre and post visitation.  But I can’t discern why
> it must be done this way — the reasoning is not documented anywhere.
> Anyone know why Stmts/Exprs are processed in this order, but not Decls and
> Types?
>

The purpose is to perform data recursion: instead of recursing using the
stack (and potentially overflowing the stack if a complex, deeply-nested
expression is encountered), a worklist is maintained separate from the
execution stack and a visitor can execute in mostly constant stack space.

This stack space optimization is automatically turned off when processing
Stmt subclasses for which the visitor defines custom behavior (if that
custom behavior doesn't support a data recursion queue) -- that's done by
the TRAVERSE_STMT_BASE macro. If you want to support more hooks that need
to turn off data recursion, you could follow a similar pattern there.


> Thanks,
>
> Dave
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20200106/213463dd/attachment-0001.html>