[llvm-bugs] [Bug 46423] New: Match callback invocation order

[via llvm-bugs]

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

            Bug ID: 46423
           Summary: Match callback invocation order
           Product: new-bugs
           Version: 10.0
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: billy.omahony at gmail.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

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 what I see is more of a breadth-first match order.


Here are my matches. Each match callback just dumps the file and line no.

    ClangTool Tool(OptionsParser.getCompilations(),
        OptionsParser.getSourcePathList());

    MyMatchCallback Mcb;
    MatchFinder Finder;

    Finder.addMatcher(
        functionDecl().bind("fn"),
        &Mcb);

    ...

    Finder.addMatcher(
        returnStmt().bind("rtn"),
        &Mcb);

    Finder.addMatcher(
        callExpr().bind("call"),
        &Mcb);

    return Tool.run(newFrontendActionFactory(&Finder).get());

I run the tool on this src file:

  1 int fn1(void) {return 1;}
  2 int fn2(void) {return 1;}
  3 int fn3(void) {return 1;}
  4 int fn4(void) {return 1;}
  5
  6 int (main)(void) {
  7     fn1();
  8     return 1;
  9
 10     if (fn2())
 11         return 1;
 12
 13     { /* arbitrary block */
 14         if(fn3())
 15             return 1;
 16     }
 17
 18     fn4();
 19
 20     return 1;
 21 }

This is the output I get:  <file>:<line_no>

    fnDecl main /home/.../match_order_test.c:6
    fn call fn1/home/.../match_order_test.c:7
    Rtn /home/.../match_order_test.c:8
    fn call fn4/home/.../match_order_test.c:18    << hey! line 10 should be
next?
    Rtn /home/.../match_order_test.c:20
    fn call fn2/home/.../match_order_test.c:10
    Rtn /home/.../match_order_test.c:11
    fn call fn3/home/.../match_order_test.c:14
    Rtn /home/.../match_order_test.c:15

I was expecting the matches to be in line-number order.

Looking at the ast-dump of the src file and adding in the order in which the
CallExprs and ReturnStmt's were matched MatchFinder looks to be doing a kind of
breadth-first traversal.

    TranslationUnitDecl 0x7fffc2a2b238 <<invalid sloc>> <invalid sloc>
    |-TypedefDecl 0x7fffc2a2bad0 <<invalid sloc>> <invalid sloc> implicit
__int128_t '__int128'
    ...
    `-FunctionDecl 0x7fffc2a8a588 <line:6:1, line:21:1> line:6:6 main 'int
(void)':'int (void)'
      `-CompoundStmt 0x7fffc2a8a8f0 <col:18, line:21:1>
    #1  |-CallExpr 0x7fffc2a8a6c0 <line:7:5, col:9> 'int'
        | `-ImplicitCastExpr 0x7fffc2a8a6a8 <col:5> 'int (*)(void)'
<FunctionToPointerDecay>
        |   `-DeclRefExpr 0x7fffc2a8a658 <col:5> 'int (void)' Function
0x7fffc2a89ef0 'fn1' 'int (void)'
    #2  |-ReturnStmt 0x7fffc2a8a700 <line:8:5, col:12>
        | `-IntegerLiteral 0x7fffc2a8a6e0 <col:12> 'int' 1
        |-IfStmt 0x7fffc2a8a798 <line:10:5, line:11:16>
    #5  | |-CallExpr 0x7fffc2a8a748 <line:10:9, col:13> 'int'
        | | `-ImplicitCastExpr 0x7fffc2a8a730 <col:9> 'int (*)(void)'
<FunctionToPointerDecay>
        | |   `-DeclRefExpr 0x7fffc2a8a710 <col:9> 'int (void)' Function
0x7fffc2a8a0c0 'fn2' 'int (void)'
    #6  | `-ReturnStmt 0x7fffc2a8a788 <line:11:9, col:16>
        |   `-IntegerLiteral 0x7fffc2a8a768 <col:16> 'int' 1
        |-CompoundStmt 0x7fffc2a8a850 <line:13:5, line:16:5>
        | `-IfStmt 0x7fffc2a8a838 <line:14:9, line:15:20>
    #7  |   |-CallExpr 0x7fffc2a8a7e8 <line:14:12, col:16> 'int'
        |   | `-ImplicitCastExpr 0x7fffc2a8a7d0 <col:12> 'int (*)(void)'
<FunctionToPointerDecay>
        |   |   `-DeclRefExpr 0x7fffc2a8a7b0 <col:12> 'int (void)' Function
0x7fffc2a8a248 'fn3' 'int (void)'
    #8  |   `-ReturnStmt 0x7fffc2a8a828 <line:15:13, col:20>
        |     `-IntegerLiteral 0x7fffc2a8a808 <col:20> 'int' 1
    #3  |-CallExpr 0x7fffc2a8a8a0 <line:18:5, col:9> 'int'
        | `-ImplicitCastExpr 0x7fffc2a8a888 <col:5> 'int (*)(void)'
<FunctionToPointerDecay>
        |   `-DeclRefExpr 0x7fffc2a8a868 <col:5> 'int (void)' Function
0x7fffc2a8a3d0 'fn4' 'int (void)'
    #4   `-ReturnStmt 0x7fffc2a8a8e0 <line:20:5, col:12>
          `-IntegerLiteral 0x7fffc2a8a8c0 <col:12> 'int' 1


David Rector, has offered some technical details as to what he thinks is
causing the issue:
http://lists.llvm.org/pipermail/cfe-dev/2020-June/065902.html

I'm using:
* Ubuntu 18.04 on Windows Subsystem for Linux. 
* http://llvm.org/git/clang-tools-extra.git 01ef2430f97631f20a702e  Fri Aug 30
20:47:02 2019 +0000
* http://llvm.org/git/llvm.git 16bef0f9a051afa7b57f5fd01624086c35ec1e60   Mon
Sep 2 16:12:31 2019 +0000

-- 
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/20200622/3471b64d/attachment.html>