[cfe-dev] Match callback invocation order

[David Rector via cfe-dev]

I took a look, the RecursiveASTVisitor-derived component is in clang/lib/ASTMatchers/ASTMatchFinder.cpp.

I am not familiar with ASTMatchers, and don’t know whether others experience the same issue Billy is experiencing, but for those who might want to fix this issue, since we’re already discussing other ways of making ASTMatchers more user-friendly out of the box, here’s what I notice in my clang 10 code:

There seem to be two visitors; a MatchASTVisitor and a MatchChildASTVisitor.  I don’t know the role of each, but both have a TraverseStmt(Stmt *S, DataRecursionQueue *Queue) implementation, which means that in either visitor, so long as a non null Queue is provided to the base RecursiveASTVisitor<…>::TraverseStmt call, it will be used, so that nested Stmt traversals will be out of order, confusing to Billy and others.

But, if either a) a null Queue were provided to the base RecursiveASTVisitor::TraverseStmt call, or b) the Queue parameter were eliminated altogether from the signatures of both, I would expect that there would be no queueing, everything would be done in the normal stack order that Billy and many other users expect.

Interestingly, the MatchChildASTVisitor *does* seem to have some logic to disable the Queue when the stack depth is sufficiently small, which would seem to be a great compromise that perhaps should even be in the RecursiveASTVisitor base TraverseStmt logic.

However, the MatchASTVisitor does not have this logic; it always passes the queue to the base TraverseStmt.

Billy and/or others might want to experiment with disabling the Queue parameter, or nullifying it, in MatchASTVisitor::TraverseStmt.  If that fixes things, perhaps the conditional Queue-nullifying code in MatchChildASTVisitor needs to be replicated up there.

Another possibility to consider, though unlikely it will work: if the ASTMatchers code could be contained in VisitStmt or WalkUpFromStmt in TraverseStmt, I believe the WalkUpFrom/VisitStmts are always performed in the right order, if you look closely at how the Queue is processed in RecursiveASTVisitor::TraverseStmt.

That is as far as I can dive into this, as my own "stack depth" of other issues is fairly high right now.  (I definitely would benefit from employing a "Queue" parameter in my own life :)

Good luck,

Dave

> On Jun 19, 2020, at 10:46 AM, Billy O'Mahony <billy.omahony at gmail.com> wrote:
> 
> Hi David,
> 
> thanks for that detail. I did have a quick look at the MatchFinder code in the source but couldn't see where it might be changed (typically the example of MatchFinder do not involve inheriting and specialising it) or where I might override it I did inherit from it. But last time I looked at C++ <algorithm> was the new hotness so that might be a bridge too far for me right now.
> 
> In any case, I've started a new impl using RecusiveASTVisitor and I don't have the out-of-order callback issue.
> 
> /Billy.
> 
> On Mon, 15 Jun 2020 at 22:36, David Rector via cfe-dev <cfe-dev at lists.llvm.org <mailto:cfe-dev at lists.llvm.org>> wrote:
> I am not familiar with ASTMatchers, but am with RecursiveASTVisitor and the issue seems to what some call the "data recursion" optimization that is specific to TraverseStmt.  While e.g. TraverseDecl(Decl *) and TraverseType(QualType), for statements the default signature is TraverseStmt(Stmt *, DataRecursionQueue *Queue); this queue argument is employed to avoid excessive stack depths that apparently occur with some very big expressions.  The way it works, I believe, is by enqueuing nested statements instead of processing them right away, in exactly the manner you describe.
> 
> Fortunately, it’s simple to turn off this optimization: just define a TraverseStmt(Stmt *S) in your Derived (I guess in this case, add this definition to whatever component of ASTMatchers inherits from RecursiveASTVisitor<…>). 
> 
> To avoid this confusion in the future (the same problem vexed me awhile back in a different context), It might be wise to alter the default TraverseStmt implementation so that, by default, it keeps track of the stack depth and only employs the data recursion queue when the stack depths really do get too great, and otherwise performs nested traversals in the same manner as TraverseDecl and TraverseType, if that makes sense.
> 
> Dave
> 
>> 
>> In the documentation for MatchFinder it says "The order of matches is
>> guaranteed to be equivalent to doing a pre-order traversal on the AST, and
>> applying the matchers in the order in which they were added to the
>> MatchFinder." but I can't reconcile what I see with what I found on the
>> wikipedia for 'pre-order traversal'.
>> 
>> Is this a bug?
>> 
>> How can I influence the traversal order so that my matchers fire in
>> source-code order?
>> 
>> Thanks,
>> Billy.
> 
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org <mailto:cfe-dev at lists.llvm.org>
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev <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/20200619/4368a80d/attachment.html>