[llvm-bugs] [Bug 39190] New: AST MatchFinder Does not Do Pre-order Traversal

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=39190

            Bug ID: 39190
           Summary: AST MatchFinder Does not Do Pre-order Traversal
           Product: clang
           Version: 7.0
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: libclang
          Assignee: unassignedclangbugs at nondot.org
          Reporter: lunastorm at lunastorm.tw
                CC: klimek at google.com, llvm-bugs at lists.llvm.org

The documentation of AST MatchFinder says:
"The order of matches is guaranteed to be equivalent to doing a pre-order
traversal on the AST"

https://clang.llvm.org/doxygen/classclang_1_1ast__matchers_1_1MatchFinder.html#details

After upgrade to Clang7, we noticed that the match order is changed.
For this example:

void foo()
{
    for (;;) {
        break;
    }
    for (;;) {
        break;
    }
    return;
}

Clang6's clang-query result of "m stmt()" is:
Match #1:

/Users/lunastorm/temp/foo.c:2:1: note: "root" binds here
{
^

Match #2:

/Users/lunastorm/temp/foo.c:3:5: note: "root" binds here
    for (;;) {
    ^~~~~~~~~~

Match #3:

/Users/lunastorm/temp/foo.c:3:14: note: "root" binds here
    for (;;) {
             ^

Match #4:

/Users/lunastorm/temp/foo.c:4:9: note: "root" binds here
        break;
        ^~~~~

Match #5:

/Users/lunastorm/temp/foo.c:6:5: note: "root" binds here
    for (;;) {
    ^~~~~~~~~~

Match #6:

/Users/lunastorm/temp/foo.c:6:14: note: "root" binds here
    for (;;) {
             ^

Match #7:

/Users/lunastorm/temp/foo.c:7:9: note: "root" binds here
        break;
        ^~~~~

Match #8:

/Users/lunastorm/temp/foo.c:9:5: note: "root" binds here
    return;
    ^~~~~~
8 matches.

====
While Clang7's clang-query result of "m stmt()" gives:
Match #1:

/Users/lunastorm/temp/foo.c:2:1: note: "root" binds here
{
^

Match #2:

/Users/lunastorm/temp/foo.c:3:5: note: "root" binds here
    for (;;) {
    ^~~~~~~~~~

Match #3:

/Users/lunastorm/temp/foo.c:6:5: note: "root" binds here
    for (;;) {
    ^~~~~~~~~~

Match #4:

/Users/lunastorm/temp/foo.c:9:5: note: "root" binds here
    return;
    ^~~~~~

Match #5:

/Users/lunastorm/temp/foo.c:3:14: note: "root" binds here
    for (;;) {
             ^

Match #6:

/Users/lunastorm/temp/foo.c:4:9: note: "root" binds here
        break;
        ^~~~~

Match #7:

/Users/lunastorm/temp/foo.c:6:14: note: "root" binds here
    for (;;) {
             ^

Match #8:

/Users/lunastorm/temp/foo.c:7:9: note: "root" binds here
        break;
        ^~~~~
8 matches.

====
We have a tool based on MatchFinder and relies on the pre-order traversal
guarantee.
It seems that it is related to r326624 which adds data recursion support to
TraverseStmt. Without this change there will be a stack overflow in
https://bugs.llvm.org/show_bug.cgi?id=36581

Can the MatchFinder remain the same traverse order guarantee by default, and
take a MatchFinderOption to supply the Queue parameter of TraverseStmt
optionally?
Or the RAV can be modified to traverse in pre-order without hitting stack
limit?

Thanks!

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20181005/7e072154/attachment.html>